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 maximal complete subgraph). 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}

The k-Clique Problem is simply the problem of deciding if a graph has a clique of 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 not if k is, say, |V|/2. A better one is to start with each node as a clique of one, and to merge cliques into larger cliques until there are no more possible merges to check. Two cliques A and B may be merged if each node in clique A is joined to each node in clique B.

Proof of NP-completeness

Assume that we have a polynomial time algorithm solving clique problem. Take an instance of 3CNF-SAT. 3CNF-SAT consists of a set of

n

clauses, each consisting of exactly 3 literals, each being either a variable or negated variable. It is satisfiable if we can choose literals in such a way that:

at least one literal from each clause is chosen
if literal of form $x$ is chosen, no literal of form $\neg x$ is

For each of the literals, create a graph node. Connect each node to every node in other clauses, except those with the same variable but different sign. In other words, the node is not connected with any nodes in the clause that has the same variable with the different sign. The problem of finding

n

-element clique is equivalent to finding a set of literals satisfying SAT. Because there are no edges between literals of the same clause, such a clique must contain exactly one literal from each clause. And because there are no edges between literals of the same variable but different sign, if node of literal

x

is in the clique, no node of literal of form

\neg x

is. This proves that finding

n

-element clique in

3n

-element graph is NP-Complete. For other proportions, we only have to add either nodes connected with every other (to make problem easier), or nodes not connected at all (to make problem harder).

Clique Problem

Proof of NP-completeness

See also