Clique problem

In computer science, the Clique Problem is an NP-complete problem in complexity theory.

A clique in a graph is a set of pairwise adjacent vertices. In the graph at the right, vertices 1, 2 and 5 form a clique.

The clique problem is the optimization problem of finding a clique of maximum size in a graph. The problem is a decision problem, so we wonder if a clique of size k exists in the graph.

CLIQUE = {<G, k>| G is a graph with a clique of size at least k}

A brute force algorithm to find a clique in a graph is to list all subsets of vertices, V and check each one to see if it forms a clique. The algorithm is polynomial if k is constant, but not if k is, say, |V|/2.

Proof

• TODO

See also

• Graph theory