<p>How about the following transformation: Given a graph $G(V,E)$ with $V=\{1,\ldots,n\}$ construct $G'(V',E')$ as follows: $V'$ initially consists of two sets of vertices: the vertices $u_i, 1\le i\le n$ and the vertices $v_{i,j}, 1\le i,j\le n$ (a total of $n^2+n$ vertices). We add the following sets of edges: first, connect all $v_{i,j}$ with $v_{i,k}$ for $k\neq j$, so the graph now consists of $n$ cliques of order $n$ and $n$ isolated vertices. Next, for all $i$, connect $u_i$ with the vertex $v_{i,i}$. Then, for all $i$ connect $u_i$ with all vertices $v_{j,i}$ for which $(i,j)\in E$. On the other hand, for all $i,j$ such that $(i,j)\not\in E$ construct a new vertex $v'_{i,j}$ and connect it to $v_{i,j}$ (this constructs two new degree-1 vertices for each non-edge of $G$). This completes the construction.</p>

<p>The claim is that $G'$ has a vertex cover of size $n(n-1)+k$ if and only if $G$ has a dominating set of size $k$. The intuition is that any vertex cover must take at least $n-1$ vertices from each clique (giving at least $n(n-1)$ vertices overall), allowing us to select exactly $k$ of the $u_i$ vertices to represent the dominating set. The vertex that is left out of the $i$-th clique encodes the vertex of the original graph that was used to dominate $i$. Observe that the leaves $v'_{i,j}$ ensure that vertices corresponding to non-edges are not left out of the vertex cover. </p>

<p>Thus, the direction dominating set of $G$ $\to$ vertex cover of $G'$ is straightforward: select the vertices from $u_i$ that represent the dominating set and from each clique select all vertices except the one that is adjacent to a selected $u_i$. For the converse direction, first note that it is never optimal to take a $v'_{i,j}$ vertex in the vertex cover since these vertices have degree 1, so their neighbors must be selected. Second, observe that in any vertex cover that selects all $n$ vertices of a clique we can exchange one of them with its neighboring $u_i$ vertex, therefore we can assume that an optimal vertex cover selects $k$ such $u_i$ vertices. These must be a dominating set of $G$.</p>

CC BY-SA 3.0
2014-07-29T08:02:25.180Z
Thank you. I implemented this and it doesn't work for $C_4$ for me. VC is $v_{i,j}$ of size $n(n-1)$. Do you get experimental support for $C_4$?
joro
CC BY-SA 3.0
2014-07-29T11:37:24.203Z
Oops, you are right! The problem was that the vertex cover was allowed to leave out a $v_{i,j}$ that corresponded to a non-edge. I think I fixed this by attaching a leaf to each such vertex, forcing it to by included in the cover.
Michael Lampis
CC BY-SA 3.0
2014-07-29T12:25:18.247Z
This fixes $C_4$ and other examples. Just to make sure: usually $(i,j)$ and $(j,i)$ are considered the same edge. You add $v'$ for both, right?
joro
CC BY-SA 3.0
2014-07-29T12:50:16.753Z
Yes. Of course, a potentially simpler solution would be to just delete the vertices $v_{i,j}$ from the graph, for $(i,j)\not\in E$.
Michael Lampis
CC BY-SA 3.0
2014-08-02T11:37:29.113Z
The other potential solution doesn't appear to work for me experimentally.
joro
CC BY-SA 3.0
2014-07-28T16:32:19.767Z
2014-07-29T11:36:18.033Z
2014-07-29T11:36:18.033Z
Michael Lampis
<blockquote>
  <p>Is there simple reduction Dominating Set to Vertex Cover?</p>
</blockquote>

<p>In the other direction the reduction is simple.</p>

<p>Searching the web returned <a href="http://standardwisdom.com/softwarejournal/np-completeness-reductions/dominating-set-to-vertex-cover/" rel="nofollow">blog</a>.</p>

<p>It warns <em>This is not finished yet</em> and experiments suggest
the reduction doesn't work.</p>

<hr>

<p><strong>Added</strong> by "simple" I mean graph transformation
$G \to G'$, s.t. $G$ has DS of size $k$ iff $G'$
has VC of size $f(G,k)$ and the transformation
does not depend on $k$ (to avoid reduction to SAT).</p>

CC BY-SA 3.0
2014-07-27T08:17:38.270Z
Can you share the example you have for which the reduction fails?
R B
CC BY-SA 3.0
2014-07-27T08:20:18.543Z
@RB If I implemented the reduction correctly, it fails for $K_4$.
joro
CC BY-SA 3.0
2014-07-27T08:42:45.260Z
Indeed. Even for $K_3$ it doesn't work.
R B
CC BY-SA 3.0
2014-12-03T22:45:50.330Z
It seems that my answer for this question: http://cstheory.stackexchange.com/questions/27692/minimal-polynomial-reduction-of-dominating-set-to-max-clique/27694#27694
gives an alternative answer. At a glance, the two reductions look pretty similar.
daniello
<graph-theory><reductions>
Is there simple reduction Dominating Set to Vertex Cover?
joro
# Is there simple reduction Dominating Set to Vertex Cover?

(Asked by: username_0 on 2014-07-27)

> Is there simple reduction Dominating Set to Vertex Cover?

In the other direction the reduction is simple.

Searching the web returned [blog](http://standardwisdom.com/softwarejournal/np-completeness-reductions/dominating-set-to-vertex-cover/).

It warns *This is not finished yet* and experiments suggest
the reduction doesn't work.

---

**Added** by "simple" I mean graph transformation
$G \to G'$, s.t. $G$ has DS of size $k$ iff $G'$
has VC of size $f(G,k)$ and the transformation
does not depend on $k$ (to avoid reduction to SAT).

**Tags:** graph-theory, reductions

> **Comments:**
> **username_1**: Can you share the example you have for which the reduction fails?  
> **username_0**: @RB If I implemented the reduction correctly, it fails for $K_4$.  
> **username_1**: Indeed. Even for $K_3$ it doesn't work.  
> **username_2**: It seems that my answer for this question: http://cstheory.stackexchange.com/questions/27692/minimal-polynomial-reduction-of-dominating-set-to-max-clique/27694#27694 gives an alternative answer. At a glance, the two reductions look pretty similar.  

---

## 1 answers

### Answer by username_3 on 2014-07-28. Score: 2

How about the following transformation: Given a graph $G(V,E)$ with $V=\{1,\ldots,n\}$ construct $G'(V',E')$ as follows: $V'$ initially consists of two sets of vertices: the vertices $u\_i, 1\le i\le n$ and the vertices $v\_{i,j}, 1\le i,j\le n$ (a total of $n^2+n$ vertices). We add the following sets of edges: first, connect all $v\_{i,j}$ with $v\_{i,k}$ for $k\neq j$, so the graph now consists of $n$ cliques of order $n$ and $n$ isolated vertices. Next, for all $i$, connect $u\_i$ with the vertex $v\_{i,i}$. Then, for all $i$ connect $u\_i$ with all vertices $v\_{j,i}$ for which $(i,j)\in E$. On the other hand, for all $i,j$ such that $(i,j)\not\in E$ construct a new vertex $v'\_{i,j}$ and connect it to $v\_{i,j}$ (this constructs two new degree-1 vertices for each non-edge of $G$). This completes the construction.

The claim is that $G'$ has a vertex cover of size $n(n-1)+k$ if and only if $G$ has a dominating set of size $k$. The intuition is that any vertex cover must take at least $n-1$ vertices from each clique (giving at least $n(n-1)$ vertices overall), allowing us to select exactly $k$ of the $u\_i$ vertices to represent the dominating set. The vertex that is left out of the $i$-th clique encodes the vertex of the original graph that was used to dominate $i$. Observe that the leaves $v'\_{i,j}$ ensure that vertices corresponding to non-edges are not left out of the vertex cover.

Thus, the direction dominating set of $G$ $\to$ vertex cover of $G'$ is straightforward: select the vertices from $u\_i$ that represent the dominating set and from each clique select all vertices except the one that is adjacent to a selected $u\_i$. For the converse direction, first note that it is never optimal to take a $v'\_{i,j}$ vertex in the vertex cover since these vertices have degree 1, so their neighbors must be selected. Second, observe that in any vertex cover that selects all $n$ vertices of a clique we can exchange one of them with its neighboring $u\_i$ vertex, therefore we can assume that an optimal vertex cover selects $k$ such $u\_i$ vertices. These must be a dominating set of $G$.

> **Comments:**
> **username_0**: Thank you. I implemented this and it doesn't work for $C_4$ for me. VC is $v_{i,j}$ of size $n(n-1)$. Do you get experimental support for $C_4$?  
> **username_3**: Oops, you are right! The problem was that the vertex cover was allowed to leave out a $v_{i,j}$ that corresponded to a non-edge. I think I fixed this by attaching a leaf to each such vertex, forcing it to by included in the cover.  
> **username_0**: This fixes $C_4$ and other examples. Just to make sure: usually $(i,j)$ and $(j,i)$ are considered the same edge. You add $v'$ for both, right?  
> **username_3**: Yes. Of course, a potentially simpler solution would be to just delete the vertices $v_{i,j}$ from the graph, for $(i,j)\not\in E$.  
> **username_0**: The other potential solution doesn't appear to work for me experimentally.  

---

