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
See also