VC ≤p DS | Complexity Atlas

The construction

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

For every edge $xy\in E$ : add a new vertex $v_{xy}$ and join it to $x$ and to $y$ .
Remove all isolated vertices from the resulting graph, and return $\hat G=(\hat V,\hat E)$ with the same $k$ .

What $v_{xy}$ does, in one line: it forces one of $x,y$ to be inside. That is the whole reduction — translating "every edge is touched" into "every vertex is dominated", by turning each edge into a vertex that demands domination.

Why step 2 is needed. An isolated vertex of $G$ touches no edge and is therefore never required in a cover; in a dominating set, by contrast, an isolated vertex must join the set, since it has no neighbour to cover it. Without step 2 we would force $\mathrm{DS}$ to add vertices with no counterpart on the $\mathrm{VC}$ side, breaking answer preservation. Since removing isolated vertices does not change the $\mathrm{VC}$ answer (the edges are untouched), we may assume from here on that $G$ has none.

The structural property used repeatedly: every new vertex $v_{xy}$ has exactly two neighbours in $\hat G$ , namely $x$ and $y$ , both in $V$ .

Visualization

⟨G, k = 2⟩ ∈ VC ?

original vertex of V

Correctness — both directions

VC ∈ ⟹ DS ∈

Suppose $\langle G,k\rangle\in\mathrm{VC}$ . Then some $U\subseteq V$ has $\forall e\in E:\ e\cap U\ne\emptyset$ and $|U|\le k$ .

Consider the same $U$ as a subset of $\hat V$ (legitimate, since $V\subseteq\hat V$ ). We show it dominates $\hat G$ . Let $x\in\hat V$ and suppose $x\notin U$ (if $x\in U$ there is nothing to prove).

Case 1: $x\in V$ . Since $G$ has no isolated vertices, some $y\in V$ has $xy\in E$ . As $U$ is a cover, $x\in U$ or $y\in U$ ; we assumed $x\notin U$ , so $y\in U$ . And $xy\in E\subseteq\hat E$ . So $x$ has a neighbour in $U$ .

Case 2: $x\notin V$ . Then $x$ was created in step 1, so there are $a,b\in V$ with $ab\in E$ and $x=v_{ab}$ . As $U$ is a cover, $a\in U$ or $b\in U$ ; and by construction $ax\in\hat E$ and $bx\in\hat E$ . So some $y\in\{a,b\}\cap U$ has $xy\in\hat E$ — $x$ has a neighbour in $U$ .

Either way $x\in U$ or $x$ has a neighbour in $U$ ; so $U$ dominates $\hat G$ , and its size $|U|\le k$ is unchanged. Hence $\langle\hat G,k\rangle\in\mathrm{DS}$ .

DS ∈ ⟹ VC ∈

Suppose some $\hat U\subseteq\hat V$ dominates $\hat G$ with $|\hat U|\le k$ .

Here $\hat U$ cannot be taken as it stands — it may contain new vertices, so it is not a subset of $V$ and certainly not a cover of $G$ . Build $U\subseteq V$ from it:

> For each $x\in\hat U$ : if $x\in V$ — put $x$ into $U$ ; if $x\notin V$ — put in one of its neighbours (by a fixed arbitrary rule; the choice does not matter).

$U\subseteq V$ : for $x\in\hat U\setminus V$ both neighbours lie in $V$ , and in the first case we inserted $x\in V$ itself.

Size: each element of $\hat U$ contributed at most one element, so $|U|\le|\hat U|\le k$ . (The same vertex may be inserted twice, making $|U|$ strictly smaller — which only helps, since an upper bound is what is needed.)

$U$ is a vertex cover of $G$ : let $xy\in E$ and suppose $x\notin U$ ; we show $y\in U$ .

First, $x\notin U$ together with $x\in V$ forces $x\notin\hat U$ — had $x$ been in $\hat U$ , the construction would have put it into $U$ .

Now consider $v_{xy}\in\hat V$ ; it exists, since $xy\in E$ so step 1 created it. As $\hat U$ dominates, either $v_{xy}\in\hat U$ or some neighbour of it lies in $\hat U$ .

Case 1: $v_{xy}\in\hat U$ . Then building $U$ we inserted one of its neighbours — $x$ or $y$ . Since $x\notin U$ , it must have been $y$ , so $y\in U$ .

Case 2: a neighbour of $v_{xy}$ lies in $\hat U$ . Its neighbours are exactly $x$ and $y$ , both in $V$ . Since $x\notin\hat U$ , necessarily $y\in\hat U$ ; and as $y\in V$ , the construction inserted $y$ itself into $U$ .

Either way $y\in U$ , so $xy\cap U\ne\emptyset$ . As $xy$ was arbitrary, $U$ is a cover of size $\le k$ , i.e. $\langle G,k\rangle\in\mathrm{VC}$ .

Cost of the reduction

TimeO(|V| + |E|)

SpaceO(|V| + |E|)

Output size|V̂| ≤ |V| + |E|, |Ê| ≤ 3|E|

The loop runs $|E|$ times, adding one vertex and two edges per iteration — constant time (or $O(\log)$ in a sensible representation). Spotting isolated vertices is a single pass over the adjacency lists, $O(|V|+|E|)$ . The output is polynomial too, which is necessary — otherwise it could not be written in polynomial time.

What it buys

$\mathrm{DS}$ is NP-hard, and being in $\mathrm{NP}$ as well, NP-complete.

Pitfalls

The identity reduction fails. A dominating set need not cover edges: the two notions come apart as soon as a vertex can be dominated by a neighbour without any incident edge being covered by it. The direction that breaks is the one requiring a translation between "touching an edge" and "dominating a vertex" — which is precisely the job of the edge vertex $v_{xy}$ .
A reduction does not solve. The algorithm $R$ knows neither $U$ nor $\hat U$ — those appear only in the correctness proof, where a solution may be assumed and turned into one for the other side.

The chain

Rests on

IS ≤p VC

Where this was read from

Lesson 19משפט 4: $\mathrm{VC}\le_p\mathrm{DS}$ , ולכן $\mathrm{DS}$ היא NP-שלמה
2025Defining $\mathrm{DS}$ and proving it hard.