Clique Decision Problem

Definition

Clique Decision Problem

Let be a graph and , whereby is part of the input (not a constant). The clique problem is a decision problem asking whether there exists a clique of , such that .

Relation to Independent Set

Let be a graph and let be its complement graph. A subset is a clique of if and only if is an independent set of .

Equivalence to Independent Set Problem

The clique problem is equivalent (w.r.t. polynomial time reduction) to the independent set problem.

Let be an instance of the independent set problem.

In polynomial time, we generate , an instance of the clique problem, where is the complement graph of . The reduction is correct since has an independent set of size if and only if has a clique of size .

The reduction operates in polynomial time since constructing the complement graph requires at most operations.

Let be an instance of the clique problem.

In polynomial time, we generate , an instance of the independent set problem. The reduction is correct since has a clique of size if and only if has an independent set of size .

This reduction is also computed in time.

Approaches

Brute-force

A brute-force approach tests all subsets of size and requires time to test whether all pairs of vertices in the subset are connected by an edge.

Time complexity: