Vertex Cover to Dominating Set (Karp Reduction)

Definition

Vertex Cover to Dominating Set

There is a polynomial-time many-one reduction from the Vertex Cover problem to the Dominating Set problem:

$$\mathrm{VERTEX}\mathrm{COVER}{\le }_m^p\mathrm{DOMINATING}\mathrm{SET}.$$

Construction

Given a vertex cover instance $(G,k)$ with $G=(V,E)$, first remove trivial thresholds. If $k<0$, output a fixed no-instance of Dominating Set; if $k\ge |V|$, output a fixed yes-instance. A single isolated vertex with threshold $0$ and threshold $1$, respectively, supplies these fixed instances.

It remains to consider $0\le k<|V|$. Construct a graph $H$ as follows:

1. Retain every original vertex $v\in V$.
2. Add a vertex $x$, join it to every original vertex, and attach $k+2$ new leaves ${\ell }_1,\dots ,{\ell }_{k+2}$ to $x$. The vertex $x$ dominates the original vertices and the leaves.
3. For every original edge $e=\{u,v\}\in E$, introduce a subdivision vertex $s_e$ and replace $e$ by the two edges $\{u,s_e\}$ and $\{s_e,v\}$. The vertex $x$ is not adjacent to any $s_e$.
4. Output the Dominating Set instance $$(H,k+1).$$

Equivalently,

$$\begin{array}{rl}V(H)& =V\cup \{x\}\cup \{{\ell }_1,\dots ,{\ell }_{k+2}\}\cup \{s_e:e\in E\},\\ E(H)& =\{\{x,v\}:v\in V\}\cup \{\{x,{\ell }_i\}:1\le i\le k+2\}\\ & \cup \{\{u,s_e\},\{s_e,v\}:e=\{u,v\}\in E\}.\end{array}$$

The vertex $x$ dominates every original vertex and every leaf. The chosen original vertex $b$ dominates both subdivision vertices, exactly as it covers both original edges.

Why the New Vertex Is Forced

Any dominating set of size at most $k+1$ must contain $x$. If it omitted $x$, each of the $k+2$ leaves would have to be selected because a leaf has no neighbour other than $x$. This would already require $k+2$ vertices, exceeding the budget.

Correctness

The graph $G$ has a vertex cover of size at most $k$ if and only if $H$ has a dominating set of size at most $k+1$.

Correctness

Forward

Suppose that $G$ has a vertex cover $C$ with $|C|\le k$. Set

$$D=C\cup \{x\}.$$

The vertex $x$ dominates itself, every original vertex, and every leaf. For each edge $e=\{u,v\}$, the cover $C$ contains $u$ or $v$, so the corresponding subdivision vertex $s_e$ is also dominated. Hence, $D$ is a dominating set with $|D|\le k+1$.

Backward

Suppose that $H$ has a dominating set $D$ with $|D|\le k+1$. The leaf gadget forces $x\in D$. Discard any selected leaves. Whenever $D$ contains a subdivision vertex $s_e$ for $e=\{u,v\}$, replace it by either endpoint $u$ or $v$. These replacements do not increase the number of selected vertices.

Let $C\subseteq V$ be the resulting set of original vertices after removing $x$. Then $|C|\le k$. Every subdivision vertex $s_e$ had to be dominated by itself or by one of its endpoints because $x$ is not adjacent to it. After the replacements, $C$ therefore contains an endpoint of every original edge $e$. Hence, $C$ is a vertex cover of $G$.

Running Time

After the trivial thresholds are removed, we have $0\le k<|V|$. The construction adds one forced vertex, $k+2=O(|V|)$ leaves, and one subdivision vertex per edge. It creates

$$O(|V|+|E|)$$

vertices and edges and can be computed in polynomial time.

NP-completeness

Vertex Cover is NP-hard, so this reduction proves that Dominating Set is NP-hard. Together with membership in NP, this proves that Dominating Set is NP-complete.