VC ≤p MODEST | Complexity Atlas

The construction

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

For every vertex $v\in V$ add a new vertex $\ell_v$ (a leaf) and the single edge $\{v,\ell_v\}$ .
Return the resulting graph $G'$ and the same $k$ .

What the leaf does. Without leaves, a surviving vertex with a single neighbour would itself be "modest" and the problem would weaken. The leaf ensures every surviving original vertex is already spending its full degree allowance: its degree is at least $1$ thanks to the leaf. So if two adjacent original vertices both survive, at least one reaches degree $2$ — and the graph is not modest. In other words: the removed set must hit every original edge, i.e. be a vertex cover.

Visualization

⟨G, k = 3⟩ ∈ VC ?modest ⇔ every degree ≤ 1

original vertex of V (large circle)original edge of E

Correctness — both directions

VC ∈ ⟹ MODEST ∈

Suppose $\langle G,k\rangle\in\mathrm{VC}$ ; take a cover $U\subseteq V$ with $|U|\le k$ . Remove exactly $U$ from $G'$ and check the remainder is modest.

Let $w$ be a surviving vertex and compute its degree in the remainder.

If $w=\ell_v$ is a leaf: its only neighbour anywhere is $v$ , so its degree is $\le1$ . ✓
If $w=v\in V\setminus U$ : its neighbours in the remainder are the leaf $\ell_v$ and any $u\in V\setminus U$ with $uv\in E$ . But $U$ is a cover, so every edge $uv\in E$ has $u\in U$ or $v\in U$ ; since $v\notin U$ we get $u\in U$ , i.e. $u$ was removed. So $v$ retains no original neighbour and its degree is exactly $1$ (the leaf alone). ✓

So every degree in the remainder is $\le1$ — the graph is modest — and $|U|\le k$ vertices were removed.

MODEST ∈ ⟹ VC ∈

Suppose some $S\subseteq V'$ with $|S|\le k$ leaves a modest graph when removed. Build a cover of $G$ from it.

Replace leaves by their vertices. Define $U=\bigl(S\cap V\bigr)\ \cup\ \{\,v\ \mid\ \ell_v\in S\,\}.$ Each leaf in $S$ is swapped for the original vertex it hangs from. Then $U\subseteq V$ and $|U|\le|S|\le k$ (the map does not grow: each element of $S$ contributes at most one).

$U$ covers $G$ . Let $uv\in E$ and suppose for contradiction $u\notin U$ and $v\notin U$ . By the definition of $U$ , $u\notin S,\quad \ell_u\notin S,\quad v\notin S,\quad \ell_v\notin S .$ So all four vertices $u,\ell_u,v,\ell_v$ survived, and so did the edges $\{u,\ell_u\}$ , $\{v,\ell_v\}$ and $\{u,v\}$ (an edge survives when both endpoints do). Then the degree of $u$ in the remainder is at least $2$ — neighbours $\ell_u$ and $v$ — contradicting modesty.

Hence $u\in U$ or $v\in U$ , i.e. $U$ is a vertex cover of $G$ of size $\le k$ , so $\langle G,k\rangle\in\mathrm{VC}$ .

Cost of the reduction

TimeO(|V| + |E|)

SpaceO(|V| + |E|)

Output size2|V| vertices, |E| + |V| edges

A single pass over the vertices, one vertex and one edge each. The output is linear in the input size.

What it buys

The problem is NP-hard, and lies in $\mathrm{NP}$ (witness $S$ ; the verifier removes and checks degrees), hence NP-complete. Its minimization version admits a $3$ -approximation.

Pitfalls

Without the leaves the reduction fails. The identity does not work: on a single-edge graph, removing $0$ vertices already leaves a modest graph (degree $1$ ), while a vertex cover needs $1$ . The leaf is exactly what closes that gap.
$S$ may contain leaves. One must not assume $S\subseteq V$ — it arrived "from the sky". Swapping a leaf for its vertex is what returns us to $V$ , and exactly as in $\mathrm{VC}\le_p\mathrm{DS}$ the size only shrinks in the swap.

The chain

Rests on

IS ≤p VC

Where this was read from

2025"Prove the following decision problem is NP-complete… Hint: reduce from VC and add a leaf to every vertex."

This problem appears in no lesson; it came up in a 2025 paper together with the explicit hint. The construction above follows that hint, and the proof here is its full working out.