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.
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.
wikipedia.org dumped 2003-03-17 with terodump