Clique problem Created 2026-10-31 Updated 2026-11-05
The decision clique problem asks whether a given finite graph contains a clique with at least vertices, where is part of the input. A proposed clique can be checked by testing all pairs of its vertices for adjacency. The problem is NP-complete; the optimization version asks for a largest clique.
Taking a complement graph turns a clique into an independent set, so clique search and maximum-independent-set search encode the same combinatorial obstruction. For fixed , checking all -vertex subsets takes polynomial time in the graph size, but its exponent depends on . This does not give a polynomial-time algorithm when varies with the input.