| • Science | • People | • Locations | • Timeline |
A clique in a graph is a set of pairwise adjacent vertices. In the graph at the right, vertices 1, 2 and 5 form a clique.
The clique problem is the optimization problem of finding a clique of maximum size in a graph (the maximal complete subgraph). The problem is a decision problem, so we wonder if a clique of size k exists in the graph.
A brute force algorithm to find a clique in a graph is to list all subsets of vertices, V and check each one to see if it forms a clique. The algorithm is polynomial if k is constant, but not if k is, say, |V|/2.
A better one is to start with each node as a clique of one, and to merge cliques into larger cliques until there are no more possible merges to check. Two cliques A and B may be merged if each node in clique A is joined to each node in clique B.
Assume, that we have a polynomial time algorithm solving clique problem.
Take an instance of 3CNF-SAT. 3CNF-SAT consists of a set of clauses, each consisting of exactly 3 literals, each being either a variable or negated variable. It is satisfiable if we can choose literals in such a way that:
For each of the literals, create a graph node, and connect each node to every node in other clauses, except those with the same variable but different sign.
The problem of finding -element clique is equivalent to finding a set of literals satisfying SAT. Because there are no edges between literals of the same clause, such a clique must contain exactly one literal from each clause. And because there are no edges between literals of the same variable but different sign, if node of literal is in the clique, no node of literal of form is.
This proves that finding -element clique in -element graph is NP-Complete. For other proportions, we only have to add either nodes connected with every other (to make problem easier), or nodes not connected at all (to make problem harder).