|
In computer science, the Clique Problem is an NP-complete problem in complexity theory.
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.
- CLIQUE = {<G, k>| G is a graph with a clique of size at least k}
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.
Proof of NP-completeness
Assume, that we have a polynomial time algorithm solving clique problem.
Take an instance of 3CNF-SAT. 3CNF-SAT consists of a set of <math>n<math> 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:
- at least one literal from each clause is chosen
- if literal of form <math>x<math> is chosen, no literal of form <math>\neg x<math> is
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 <math>n<math>-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 <math>x<math> is in the clique, no node of literal of form <math>\neg x<math> is.
This proves that finding <math>n<math>-element clique in <math>3n<math>-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).
See also
| 
