2
$\begingroup$

Is there simple reduction Dominating Set to Vertex Cover?

In the other direction the reduction is simple.

Searching the web returned blog.

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

$\endgroup$
  • $\begingroup$ Can you share the example you have for which the reduction fails? $\endgroup$ – R B Jul 27 '14 at 8:17
  • 1
    $\begingroup$ @RB If I implemented the reduction correctly, it fails for $K_4$. $\endgroup$ – joro Jul 27 '14 at 8:20
  • $\begingroup$ Indeed. Even for $K_3$ it doesn't work. $\endgroup$ – R B Jul 27 '14 at 8:42
  • $\begingroup$ It seems that my answer for this question: cstheory.stackexchange.com/questions/27692/… gives an alternative answer. At a glance, the two reductions look pretty similar. $\endgroup$ – daniello Dec 3 '14 at 22:45
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – joro Jul 29 '14 at 8:02
  • $\begingroup$ 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. $\endgroup$ – Michael Lampis Jul 29 '14 at 11:37
  • $\begingroup$ 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? $\endgroup$ – joro Jul 29 '14 at 12:25
  • $\begingroup$ 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$. $\endgroup$ – Michael Lampis Jul 29 '14 at 12:50
  • $\begingroup$ The other potential solution doesn't appear to work for me experimentally. $\endgroup$ – joro Aug 2 '14 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.