Clique

Input

Graph $G = (V, E)$, positive integer $K \leq |V|$.

Question

Does $G$ contain a clique of size $K$ or more, i.e. a subset $V' \subseteq V$ with $|V'| \geq K$ such that every two vertices in $V'$ are joined by an edge in $E$?

Classes

• NP-complete

Comments

Solvable in polynomial time for graphs obeying any fixed degree bound $d$, for planar graphs, for edge graphs, for chordal graphs (Gavril, 1972), for comparability graphs, for edge graphs, for chordal graphs (Gavril, 1973), and for circular arc graphs (given their representation as families of arcs) (Gavril, 1974). The variant in which, for a given $r$, $0 < r < 1$, we are asked whether $G$ contains a clique of size $r|V|$ or more is NP-complete for any fixed value of $r$.

Proofs

NP-complete

Transformation from Vertex Cover (Karp, 1972).

Reducible from

• Vertex Cover

References

• Gavril, F. (1972). Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph. SIAM Journal on Computing, 1(2), 180–187. https://doi.org/10.1137/0201013
• Gavril, F. (1973). Algorithms for a maximum clique and a maximum independent set of a circle graph. Networks, 3(3), 261–273. https://doi.org/10.1002/net.3230030305
• Gavril, F. (1974). Algorithms on circular-arc graphs. Networks, 4(4), 357–369. https://doi.org/10.1002/net.3230040407
• Karp, R. M. (1972). Reducibility among Combinatorial Problems. In Complexity of Computer Computations (pp. 85–103). Springer US. https://doi.org/10.1007/978-1-4684-2001-2_9