6.16.1. Independent Set to Vertex Cover¶

The following slideshow shows that an input instance to INDEPENDENT SET can be reduced to an equivalent input instance to VERTEX COVER in polynomial time.

1 / 15 Settings

<<<>>>

Reduction of an input instance to INDEPENDENT SET to an equivalent input instance to VERTEX COVER.

For a given graph $G = ( V , E )$ and integer $k$, the INDEPENDENT SET problem is to find whether G contains
an Independent Set of size $\geq k$.

For a given graph $G = ( V , E )$ and integer $k$, the VERTEX COVER problem is to find whether G contains
a Vertex Cover of size $\leq k$.

In a graph $G = \{ V , E \}$,
$S$ is an Independent Set $\Leftrightarrow (V - S)$ is a Vertex Cover.

1. If $S$ is an Independent Set, there is no edge $e = (u,v)$ in $G$, such that both $u,v \in S$.
Hence for any edge $e = (u,v)$, at least one of $u, v$ must lie in $(V-S)$.
$\Rightarrow (V-S)$ is a vertex cover in G.

2. If $(V-S)$ is a Vertex Cover, then between any pair of vertices $(u,v) \in S$ if there exist an edge $e$,
none of the endpoints of $e$ would exist in $(V - S)$ violating the definition of vertex cover.
Hence no pair of vertices in $S$ can be connected by an edge.
$\Rightarrow S$ is an Independent Set in G.

Hence G contains an Independent Set of size $k$   $\Leftrightarrow $    G contains a Vertex Cover of size $\left\vert{V}\right\vert - k$.

3

1

6

2

8

4

9

5

12

11

7

10

No

Yes

Saving...
Server Error
Resubmit

This reduction can help in providing an NP Completeness proof for the Vertex Cover problem.