|
In graph theory, a clique in a undirected graph G, is a set of vertices V such that for every two vertices in V, there exists an edge connecting the two. Additionally, this means that a clique is simply a complete subgraph of G. The size of a clique is the number of vertices it contains.
The clique problem refers to the problem of finding the largest clique in any graph G. This problem is NP-complete, and as such, many consider that it is unlikely that an efficient algorithm for finding the largest clique of a graph exists.
The opposite of a clique is an independent set. If we already know that the independent set problem is NP-complete, then it is easy to prove, as the size of the largest clique is the same as the size of the largest independent set in the inverse graph.
|
