Reduction: Independent Set → Vertex Cover

To reduce INDEPENDENT SET to VERTEX COVER we just need to notice that:

• A set of nodes $S$ is a vertex cover of graph $G = (V,E)$
  • $S$ touches every edge in $E$ iff the remaining nodes $V-S$ are an independent set of $G$.

• Therefore to solve an instance $(G, g)$ of INDEPENDENT SET simply look for a vertex cover of $G$ with $|V|-g$ nodes.
  • If such a vertex cover exists, then take all nodes not in it.
  • If no such cover exists, then $G$ cannot possibly have an independent set of size $g$.