Vertex Cover Problem

algorithms

Definition

Vertex Cover Problem

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

Relation to Independent Set

Let $G=(V,E)$ be a graph and $S\subseteq V$ and $C=V-S$. $S$ is an independent set of $G$ if and only if $C$ is a vertex cover of $G$.

Equivalence to Independent Set Problem

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

$\text{VERTEX COVER}{\le }_P\text{INDEPENDENT SET}$

Let $(G,k)$ be an instance of the vertex cover problem and $n$ be the number of vertices of $G$.

In polynomial time, we generate $(G,n-k)$, an instance of the independent set problem. The reduction is correct since $G$ has a vertex cover $\le k$ if $G$ is an independent set of size $\ge n-k$.

Trivially, the reduction is polynomial, since we only replaced $n$ by $n-k$.

$\text{INDEPENDENT SET}{\le }_P\text{VERTEX COVER}$