Independent Set to Vertex Cover (Karp Reduction)

Definition

Independent Set to Vertex Cover

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

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

Construction

Given an independent set instance $(G,k)$ with $G=(V,E)$ and $n=|V|$, output the vertex cover instance

$$(G,n-k).$$

The graph remains unchanged. Only the threshold changes because a set $S\subseteq V$ and its complement $C=V\setminus S$ satisfy

$$|C|=n-|S|.$$

The orange independent set on the left becomes the unselected vertices on the right. Its complement is orange on the right and touches every edge.

Correctness

The graph $G$ has an independent set of size at least $k$ if and only if it has a vertex cover of size at most $n-k$.

Correctness

Forward

Suppose that $G$ has an independent set $S$ with $|S|\ge k$. Let $C=V\setminus S$. Since no edge has both endpoints in $S$, every edge has at least one endpoint in $C$. Thus, $C$ is a vertex cover, and

$$|C|=n-|S|\le n-k.$$

Hence, $(G,n-k)$ is a yes-instance of Vertex Cover.

Backward

Suppose that $G$ has a vertex cover $C$ with $|C|\le n-k$. Let $S=V\setminus C$. If two vertices in $S$ were adjacent, their edge would have no endpoint in $C$, contradicting that $C$ is a vertex cover. Hence, $S$ is independent, and

$$|S|=n-|C|\ge k.$$

Therefore, $(G,k)$ is a yes-instance of Independent Set.

Running time

The reduction counts the $n$ vertices, computes $n-k$, and copies the graph without changing its edges. It therefore runs in $O(|V|+|E|)$ time, which is polynomial in the input size.

NP-completeness

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