Reduction from Vertex Cover to Dominating Set

Question

I am trying to reduce the vertex cover (decision) problem to the dominating set (decision) problem in order to prove that the latter is NP-hard. After some research online, I found that many articles use a reduction that transforms the input for the vertex cover problem to an input for the dominating set problem by creating a triangle for each edge. Here is one of such articles (See question 7 in the link).

The question that I would like to ask is, if we drop isolated vertices in the input to the dominating set problem, then, we could easily find a counterexample to the reduction - Let the input to the vertex cover problem be a graph containing $N$ isolated nodes and parameter $k=N$. Now, the input to the dominating set problem will clearly be an empty graph with the parameter $k=N$. Now, there is a vertex cover of size $N$. But it is not a dominating set of the transformed graph (i.e. the answer to the vertex cover problem is yes but the answer to the dominating set cover problem is no).

How could I fix the reduction? Could someone please advise me?

Answer 1

If I understand correctly you only have a problem when the graph $G = (V,E)$ of the vertex-cover instance has isolated vertices. In this case you can transform $G$ into a related graph $G' = (V \cup \{x,y \}, E')$ by adding a two new vertices $x$ and $y$ such that $x$ and $y$ are connected to each other by an edge, and there is an edge between $x$ and each other vertex in $V$. Formally: $E' = E \cup \{ (x,v) \mid v \in V \cup \{y\}\}$.

If $G$ admits a vertex-cover $C$ of size at most $k$, then $G'$ admits a vertex-cover of size at most $k+1$, namely $C \cup \{ x \}$.

If $G'$ admits a vertex-cover $C$ of size at most $k+1$, then $G$ admits a vertex-cover of size at most $k$. This can be easily seen by noticing that $C \setminus \{ x, y\}$ must cover all the edges in $E$, and that $(x,y) \in E'$ ensures that at least one of $x$ and $y$ is in $C$, i.e., $|C \setminus \{ x, y\}| = |C| - |C \cap \{x,y\}| \le |C| - 1 \le k$.

Since $G'$ has no isolated vertex, you can now safely transform it to the graph $H$ of the dominating-set instance (using the known reduction). In this way you show that $G$ has a vertex-cover of size at most $k$ $\iff$ $H$ has a dominating set of size at most $k+1$.