# 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.

## See also