Clique problem

To find a maximum clique, one can systematically inspect all subsets, but this sort of brute-force search is too time-consuming to be practical for networks comprising more than a few dozen vertices.

For instance, complete subgraphs make an early appearance in the mathematical literature in the graph-theoretic reformulation of Ramsey theory by Erdős & Szekeres (1935).

The first algorithm for solving the clique problem is that of Harary & Ross (1957),[1] who were motivated by the sociological application.

See, for instance, Tarjan & Trojanowski (1977), an early work on the worst-case complexity of the maximum clique problem.

Also in the 1970s, beginning with the work of Cook (1971) and Karp (1972), researchers began using the theory of NP-completeness and related intractability results to provide a mathematical explanation for the perceived difficulty of the clique problem.

In the 1990s, a breakthrough series of papers beginning with Feige et al. (1991) showed that (assuming P ≠ NP) it is not even possible to approximate the problem accurately and efficiently.

[11] Listing the cliques in a dependency graph is an important step in the analysis of certain random processes.

[12] In mathematics, Keller's conjecture on face-to-face tiling of hypercubes was disproved by Lagarias & Shor (1992), who used a clique-finding algorithm on an associated graph to find a counterexample.

In particular, the problem of finding the lexicographically first maximal clique (the one found by the algorithm above) has been shown to be complete for the class of polynomial-time functions.

[28] For instance, Chiba & Nishizeki (1985) describe an algorithm that sorts the vertices in order from highest degree to lowest and then iterates through each vertex v in the sorted list, looking for triangles that include v and do not include any previous vertex in the list.

As the authors show, the time for this algorithm is proportional to the arboricity of the graph (denoted a(G)) multiplied by the number of edges, which is O(m a(G)).

More generally, all k-vertex cliques can be listed by a similar algorithm that takes time proportional to the number of edges multiplied by the arboricity to the power (k − 2).

Alon, Yuster & Zwick (1994) used fast matrix multiplication to improve the O(m3/2) algorithm for finding triangles to O(m1.41).

These algorithms based on fast matrix multiplication have also been extended to problems of finding k-cliques for larger values of k.[29] By a result of Moon & Moser (1965), every n-vertex graph has at most 3n/3 maximal cliques.

Variants of this algorithm can be shown to have worst-case running time O(3n/3), matching the number of cliques that might need to be listed.

Makino & Uno (2004) provide an alternative output-sensitive algorithm based on fast matrix multiplication.

Robson's algorithm combines a similar backtracking scheme (with a more complicated case analysis) and a dynamic programming technique in which the optimal solution is precomputed for all small connected subgraphs of the complement graph.

For perfect graphs, it is possible to find a maximum clique in polynomial time, using an algorithm based on semidefinite programming.

[43] However, this method is complex and non-combinatorial, and specialized clique-finding algorithms have been developed for many subclasses of perfect graphs.

Because the maximum clique in a random graph has logarithmic size with high probability, it can be found by a brute force search in expected time 2O(log2n).

It describes how to translate Boolean formulas in conjunctive normal form (CNF) into equivalent instances of the maximum clique problem.

[63] The computational difficulty of the clique problem has led it to be used to prove several lower bounds in circuit complexity.

It is also possible to define random and quantum decision tree complexity of a property, the expected number of questions (for a worst case input) that a randomized or quantum algorithm needs to have answered in order to correctly determine whether the given graph has the property.

[68] The Aanderaa–Karp–Rosenberg conjecture also states that the randomized decision tree complexity of non-trivial monotone functions is Θ(n2).

Moreover, this result provides the basis for proofs of W[1]-hardness of many other problems, and thus serves as an analogue of the Cook–Levin theorem for parameterized complexity.

[33] Weak results hinting that the clique problem might be hard to approximate have been known for a long time.

Garey & Johnson (1978) observed that, because the clique number takes on small integer values and is NP-hard to compute, it cannot have a fully polynomial-time approximation scheme, unless P = NP.

If too accurate an approximation were available, rounding its value to an integer would give the exact clique number.

However, little more was known until the early 1990s, when several authors began to make connections between the approximation of maximum cliques and probabilistically checkable proofs.

Two vertices are adjacent, in this graph, if the corresponding two accepting runs see the same bit values at every position they both examine.

The brute force algorithm finds a 4-clique in this 7-vertex graph (the complement of the 7-vertex path graph ) by systematically checking all C (7,4) = 35 4-vertex subgraphs for completeness.
The graph shown has one maximum clique, the triangle {1,2,5}, and four more maximal cliques, the pairs {2,3}, {3,4}, {4,5}, and {4,6}.
In this permutation graph , the maximum cliques correspond to the longest decreasing subsequences (4,3,1) and (4,3,2) of the defining permutation.
A random graph with a planted clique
The 3-CNF Satisfiability instance (x ∨ x ∨ y) ∧ (~x ∨ ~y ∨ ~y) ∧ (~x ∨ y ∨ y) reduced to Clique. The green vertices form a 3-clique and correspond to a satisfying assignment. [ 58 ]
A monotone circuit to detect a k -clique in an n -vertex graph for k = 3 and n = 4 . Each input to the circuit encodes the presence or absence of a particular (red) edge in the graph. The circuit uses one internal and-gate to detect each potential k -clique.
A simple decision tree to detect the presence of a 3-clique in a 4-vertex graph. It uses up to 6 questions of the form "Does the red edge exist?", matching the optimal bound n ( n − 1)/2.
A graph of compatibility relations among 2-bit samples of 3-bit proof strings. Each maximal clique (triangle) in this graph represents all ways of sampling a single 3-bit string. The proof of inapproximability of the clique problem involves induced subgraphs of analogously defined graphs for larger numbers of bits.