IS ≤p VC | Complexity Atlas

The construction

On input $\langle G,k\rangle$ with $G=(V,E)$ :

Return $\langle G,\ |V|-k\rangle$ .

That is all. The same graph, with only the number changed.

The construction rests on one observation, the heart of the lesson: for every $U\subseteq V$ , $U \text{ is a vertex cover of } G \iff V\setminus U \text{ is independent in } G .$ Both say exactly the same thing about every edge: "every edge has an endpoint in $U$ " is "no edge has both endpoints outside $U$ ".

Visualization

Correctness — both directions

IS ∈ ⟹ VC ∈

Suppose $\langle G,k\rangle\in\mathrm{IS}$ . Then some $U\subseteq V$ is independent in $G$ with $|U|=k$ . By the observation, $V\setminus U$ is a vertex cover of $G$ , of size $|V\setminus U|=|V|-|U|=|V|-k .$ So $G$ has a vertex cover of size $|V|-k$ , i.e. $\langle G,|V|-k\rangle\in\mathrm{VC}$ .

VC ∈ ⟹ IS ∈

Suppose $\langle G,|V|-k\rangle\in\mathrm{VC}$ . Then $G$ has a vertex cover $U\subseteq V$ with $|U|=|V|-k$ . By the observation, $V\setminus U$ is independent in $G$ , of size $|V\setminus U|=|V|-(|V|-k)=k .$ So $\langle G,k\rangle\in\mathrm{IS}$ .

Cost of the reduction

TimeO(|⟨G,k⟩|²)

SpaceO(|⟨G,k⟩|)

Output size|⟨G,k⟩| + O(1)

The algorithm copies the input and performs one subtraction. On a RAM that is even constant time; on a Turing machine it is a binary subtraction on a number no longer than the input, i.e. $O(|\langle G,k\rangle|^2)$ done naively. Polynomial either way, which is all that is required.

What it buys

$\mathrm{VC}$ is NP-hard, and being in $\mathrm{NP}$ as well (witness $U$ ; the verifier checks $|U|\le k$ and scans the edges) it is NP-complete. From there it becomes the starting point of $\mathrm{VC}\le_p\mathrm{SUBSET\text{-}SUM}$ , $\mathrm{VC}\le_p\mathrm{DS}$ , and $\mathrm{VC}\le_p\mathrm{3H\text{-}VC}$ .

Pitfalls

"Exactly $k$ " versus "at least / at most $k$ ". The proof uses sizes exactly $k$ and exactly $|V|-k$ , while the definitions say "at least $k$ " for $\mathrm{IS}$ and "at most $k$ " for $\mathrm{VC}$ . This is legitimate: a cover can always be grown (adding vertices never breaks a cover) and an independent set can always be shrunk (a subset of an independent set is independent). Note the directions are opposite between the two problems — and for every new problem the question must be asked afresh.
"Why not the identity?" — two reasons. Direction: we want a reduction into $\mathrm{VC}$ , not out of it, since the goal is to prove $\mathrm{VC}$ hard. And the number: the graph does stay the same, but $k$ must change, precisely because of the relation between a set's size and its complement's.

The chain

Rests on

3SAT ≤p IS

Used later by

Where this was read from

Lesson 10משפט 2: $\mathrm{IS} \le_p \mathrm{VC}$ , ולכן $\mathrm{VC}$ היא NP-שלמה
Guided exerciseindependent-set-to-vertex-cover
2026 '2 מועד 2The $\le_p$ relations between the "exactly", "at least", and "minimum" versions of vertex cover.