Clique problem

A clique (pronounced "click") in a graph is a set of pairwise adjacent vertices. In the example graph in Graph theory, 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 in a clique of size k exists in the graph.

CLIQUE = {<G,K>| G is a graph with clique, size 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 super-duper polynomial time if k is |V|/2.

Proof

• TODO