Reduce Independent Set to Vertex Cover

Convert an independent-set threshold into a vertex-cover threshold by complementing the chosen vertex set.

Problem

Given an undirected graph $G=(V,E)$ and integer $k$, construct in polynomial time an integer $k'$ (on the same graph, or an explicitly described isomorphic copy) such that $G$ has an independent set of size at least $k$ if and only if $G$ has a vertex cover of size at most $k'$. Prove both directions.

Hint 1

If $S$ is independent, every edge must touch $V\setminus S$.

Hint 2

Relate the two sizes by $|V|$.

Full solution

Keep the same graph $G$ and set $k'=|V|-k$. The map $(G,k)\mapsto(G,|V|-k)$ is clearly polynomial.

Claim: $S\subseteq V$ is an independent set if and only if $V\setminus S$ is a vertex cover. Indeed, $S$ is independent exactly when no edge has both endpoints in $S$, which is exactly the statement that every edge has at least one endpoint in $V\setminus S$.

Therefore $G$ has an independent set of size $k$ if and only if it has a vertex cover of size $|V|-k$. (If an independent set larger than $k$ exists one may discard vertices; dually, a smaller cover may be padded only when the language uses “at most,” which is the standard decision form here.)

Vertex Cover is in NP via a candidate cover of size $k'$. With Independent Set NP-complete, the reduction yields NP-completeness of Vertex Cover.

Checkpoint

This uses set complement on vertices, not graph complement on edges. The parameter must change: $k\mapsto |V|-k$.

Common mistakes

• Leaving $k'=k$, which reverses the intended meaning.
• Confusing Vertex Cover with Edge Cover or Dominating Set.
• Claiming the identity without checking edges that touch both $S$ and $V\setminus S$.

Provenance note

This is an independently written presentation of the standard IS/VC duality taught in the course graph-problems lectures and aligned with Sipser / Garey–Johnson. It is not transcribed from a single exam prompt.

Sources and verification

• Merged summary, pp. 55-57
• Sipser 3e, sec. 7.5
• Garey-Johnson, GT1 and GT20
• Catalog mapping: data/exercises.json; statements and solutions are independently written.

Open in the visualization gallery: Independent Set → Vertex Cover