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$
4
  • $\begingroup$ Can you share the example you have for which the reduction fails? $\endgroup$
    – R B
    Jul 27, 2014 at 8:17
  • 1
    $\begingroup$ @RB If I implemented the reduction correctly, it fails for $K_4$. $\endgroup$
    – joro
    Jul 27, 2014 at 8:20
  • $\begingroup$ Indeed. Even for $K_3$ it doesn't work. $\endgroup$
    – R B
    Jul 27, 2014 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, 2014 at 22:45

1 Answer 1

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$
5
  • $\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, 2014 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$ Jul 29, 2014 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, 2014 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$ Jul 29, 2014 at 12:50
  • $\begingroup$ The other potential solution doesn't appear to work for me experimentally. $\endgroup$
    – joro
    Aug 2, 2014 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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