Reduction from Vertex Cover to Dominating Set

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).

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$$.

• Amazing answer. Thank you! Nov 26, 2019 at 1:49