The clique problem belongs to the class of NP-complete problems in the field of graph theory . It was first formulated in 1972 by Richard Karp . [one]
A clique in an undirected graph is a subset of vertices, each two of which are connected by an edge of the graph. In other words, this is a complete subgraph of the original graph. The size of a clique is defined as the number of vertices in it. The clique problem exists in two versions: in the recognition problem it is required to determine whether a clique of size k exists in a given graph G , while in the computational version it is necessary to find a clique of maximum size in a given graph G.
Content
NP completeness
The NP-completeness of the clique problem follows from the NP-completeness of the problem of an independent set (vertices). It is easy to show that a necessary and sufficient condition for the existence of a clique of size k is the existence of an independent set of size at least k in the complement of the graph. This is obvious, since the completeness of the subgraph means that its complement does not contain any edges.
Other evidence of NP completeness can be found in the book Algorithms: Construction and Analysis. [2]
Algorithms
As for other NP-complete tasks, an effective algorithm for searching for clicks of a given size has not yet been found. A exhaustive search of all possible subgraphs of size k with a check to see if at least one of them is complete is inefficient, since the total number of such subgraphs in a graph with v vertices is equal to the binomial coefficient
Another algorithm works like this: two clicks of size n and m “stick together” into a large clique of size n + m , and a click of size 1 relies on a separate vertex of the graph. The algorithm ends as soon as no merge can be made anymore. The running time of this algorithm is linear, but it is heuristic, since it does not always lead to finding a click of maximum size. As an example of unsuccessful completion, we can cite the case when the vertices belonging to the maximum clique are divided and are in smaller cliques, and the latter can no longer be “glued” to each other.
See also
- Bron - Kerbosch algorithm - quick click detection
Notes
- ↑ Karp, Richard (1972). " Reducibility Among Combinatorial Problems ". Proceedings of a Symposium on the Complexity of Computer Computations , Plenum Press.
- ↑ Kormen, T. , Leiserson, C. , Rivest, R. , Stein, K. Algorithms: construction and analysis = Introduction to Algorithms / Ed. I.V. Krasikova. - 2nd ed. - M .: Williams, 2005 .-- 1296 p. - ISBN 5-8459-0857-4 .
Literature
- Cook, Stephen A. (1971). " The Complexity of Theorem-Proving Procedures ". Proceedings of the Third Annual ACM Symposium on Theory of Computing : 151-158. Retrieved 2007-06-11 . Archived May 3, 2006 on the Wayback Machine
- Garey, Michael R. & Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , WH Freeman, ISBN 0-7167-1045-5 A1.2: GT19, pg. 194.