Clique problem (source code)

= Clique problem
{wiki}

The decision <clique problem> asks whether a given finite <graph> contains a <clique> with at least $k$ vertices, where $k$ 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 $k$, checking all $k$-vertex subsets takes polynomial time in the graph size, but its exponent depends on $k$. This does not give a polynomial-time algorithm when $k$ varies with the input.