Clique problem
In computational complexity theory, the clique problem is a graph-theoretic NP-complete problem. The problem was one of Richard Karp's original 21 problems shown NP-complete in his 1972 paper "Reducibility Among Combinatorial Problems". This problem was also mentioned in Cook's paper introducing the theory of NP-complete problems.
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 .
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 adjacent 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. 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(n1.41) algorithm where n is the number of edges.[1]
See also
References
- ^ Note that the k-clique problem: the problem of finding whether a k-clique is present in a graph G or not is exponential in k (and not in the order of the graph G). Alon, N.; Yuster, R.; Zwick, U. (1997), "Finding and counting given length cycles", Algorithmica, 17: 209–223, doi:10.1007/BF02523189
- Cook, Stephen A. (1971). "The Complexity of Theorem-Proving Procedures". Proceedings of the Third Annual ACM Symposium on Theory of Computing. Shaker Heights, Ohio. pp. 151–158. Retrieved 2007-06-11.
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help) - Karp, Richard (1972). "Reducibility Among Combinatorial Problems". Proceedings of a Symposium on the Complexity of Computer Computations. Plenum Press.
{{cite conference}}: Unknown parameter|booktitle=ignored (|book-title=suggested) (help) - Garey, Michael R.; Johnson, David S. (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.