Independent Set to Clique (Karp Reduction)

Definition

Independent Set to Clique

There is a polynomial-time many-one reduction from the Independent Set problem to the Clique problem:

$$\mathrm{INDEPENDENT}\mathrm{SET}{\le }_m^p\mathrm{CLIQUE}.$$

Construction

Given an independent set instance $(G,k)$ with $G=(V,E)$, output the clique instance

$$(H,k)=(\overline{G},k),$$

where $H=\overline{G}=(V,\overline{E})$ is the complement graph of $G$:

$$\overline{E}=\left(\genfrac{}{}{0ex}{}{V}{2}\right)\setminus E.$$

Thus, $H$ has the same vertices as $G$. Every edge of $G$ becomes a non-edge of $H$, and every non-edge between distinct vertices of $G$ becomes an edge of $H$. The threshold $k$ remains unchanged.

The highlighted vertices have no edges between them in $G$. Complementation inserts exactly those missing edges, so the same vertex set forms a clique in $H$.

Correctness

The graph $G$ has an independent set of size at least $k$ if and only if its complement $H$ has a clique of size at least $k$.

Correctness

Forward

Suppose that $G$ has an independent set $S$ with $|S|\ge k$. For every distinct $u,v\in S$, the pair $\{u,v\}$ is not an edge of $G$. It is therefore an edge of $H=\overline{G}$. Hence every pair of vertices in $S$ is adjacent in $H$, so $S$ is a clique of size at least $k$.

Backward

Suppose that $H$ has a clique $C$ with $|C|\ge k$. For every distinct $u,v\in C$, the pair $\{u,v\}$ is an edge of $H$ and therefore not an edge of $G$. Hence no two vertices in $C$ are adjacent in $G$, so $C$ is an independent set of size at least $k$.

Running time

Let $n=|V|$. Constructing $H$ requires inspecting each of the $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ unordered pairs of distinct vertices and reversing its adjacency status. The reduction therefore runs in $O(n^2)$ time and produces at most $O(n^2)$ edges, which is polynomial in the input size.

NP-completeness

Independent Set is NP-hard, so this reduction proves that Clique is NP-hard. Together with membership in NP, this proves that Clique is NP-complete.