Clique problem

In computational complexity theory, the clique problem is a graph-theoretical NP-complete problem. The problem was not only one of Richard Karp's original 21 problems shown NP-complete in his seminal 1972 paper "Reducibility Among Combinatorial Problems", but was even mentioned in Cook's paper introducing the theory of NP-complete problems.

A clique of size 3.

A clique in a graph is a set of pairwise adjacent vertices, or in other words, an induced subgraph which is a complete graph. In the graph at the right, vertices 1, 2 and 5 form a clique, because each has an edge to all the others.

Then, the clique problem is the problem of determining whether a graph contains a clique of at least a given size k. Once we have located k or more vertices which form a clique, it's trivial to verify that they do, which is why the clique problem is in NP. The corresponding optimization problem, the maximum clique problem, is to find the largest clique in a graph.

The NP-completeness of the clique problem follows trivially from the NP-completeness of the independent set problem, because there is a clique of size at least k if and only if there is an independent set of size at least k in the complement graph. This is easy to see, since if a subgraph is complete, its complement subgraph has no edges at all.

Algorithms

A brute force algorithm to find a clique in a graph is to examine each subgraph with at least k vertices and check to see if it forms a clique. This algorithm is polynomial if k is the number of vertices, or a constant less than this, but not if k is, say, half the number of vertices; the number of possible cliques of size k on a graph of size V is equal to ${V \choose k}={\frac {V!}{k!(V-k)!}}$.

A heuristic is to start by considering each node to be a clique of size one, and to merge cliques into larger cliques until there are no more possible merges. Two cliques A and B may be merged if each node in clique A is joined to each node in clique B. This requires only linear time (linear in the number of edges), but may fail to find a large clique because two or more parts of the large clique have already been merged with nodes that are not in the clique. It does, however, find at least one maximal clique, which is a clique not contained in any larger clique. The algorithm can be implemented most efficiently using the union-find algorithm.

Some special cases may be solved in less than exponential time. For k = 3, there exists an O(n^1.41) algorithm where n is the number of edges.

See also

• Combinatorics
• Ramsey Theory
• Theorem on friends and strangers

References

• Alon, Noga; Yuster, Raphael; Zwick, Uri (1998-08-09), Finding and counting given length cycles, retrieved 2007-02-14 {{citation}}: Check date values in: |date= (help)CS1 maint: date and year (link)
• Richard Karp. Reducibility Among Combinatorial Problems. Proceedings of a Symposium on the Complexity of Computer Computations. 1972.
• Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman. ISBN 0-7167-1045-5. A1.2: GT19, pg.194.

External links

• Challenging Benchmarks for Maximum Clique, Maximum Independent Set, Minimum Vertex Cover and Vertex Coloring