Clique Problem

computation graph-theory

Definition

Clique Problem

Let $G=(V,E)$ be a graph and $k\in \mathbb{Z}$, whereby $k$ is part of the input (not a constant). The clique problem is a decision problem asking whether there exists a clique $C\subseteq V$ of $G$, such that $|C|\ge k$.

Relation to Independent Set

Let $G=(V,E)$ be a graph and let $\bar{G}=(V,\bar{E})$ be its complement graph. A subset $C\subseteq V$ is a clique of $G$ if and only if $C$ is an independent set of $\bar{G}$.

Equivalence to Independent Set Problem

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

$\text{INDEPENDENT SET}{\le }_P\text{CLIQUE}$

Let $(G,k)$ be an instance of the independent set problem.

In polynomial time, we generate $(\bar{G},k)$, an instance of the clique problem, where $\bar{G}$ is the complement graph of $G$. The reduction is correct since $G$ has an independent set of size $\ge k$ if and only if $\bar{G}$ has a clique of size $\ge k$.

The reduction operates in polynomial time since constructing the complement graph $\bar{G}$ requires at most $O(|V{|}^2)$ operations.

$\text{CLIQUE}{\le }_P\text{INDEPENDENT SET}$

Let $(G,k)$ be an instance of the clique problem.

In polynomial time, we generate $(\bar{G},k)$, an instance of the independent set problem. The reduction is correct since $G$ has a clique of size $\ge k$ if and only if $\bar{G}$ has an independent set of size $\ge k$.

This reduction is also computed in $O(|V{|}^2)$ time.

Approaches

Brute-force

A brute-force approach tests all $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=O(n^k)$ subsets of size $k$ and requires $O(k^2)$ time to test whether all pairs of vertices in the subset are connected by an edge.

Time complexity: $O(k^2{n}^k)$