Although the reduction from vertex cover problem to set cover problem is quite simple, I did not find anywhere the reduction in the opposite direction. From the similarity in the type of problems, I guess this reduction should be simple too. However, despite trying for some time, I could not develop this. So, any ideas how this reduction can be done?
-
$\begingroup$ This reduction to another graph covering problem may give you some ideas. $\endgroup$ – Raphael♦ Aug 29 '12 at 0:14
-
$\begingroup$ I think a reduction from set cover to vertex cover in a hypergraph may be easier, en.wikipedia.org/wiki/Hypergraph; that is, although an edge connects a pair of vertices, a hyperedge in a hypergraph connects an arbitrary set of vertices (not just a pair). $\endgroup$ – Joe Sep 7 '12 at 19:41
-
$\begingroup$ If the reduction to hypergraph-vertex-cover works, then maybe you can also use the fact that any hypergraph can be represented by a bipartite graph? en.wikipedia.org/wiki/Hypergraph#Bipartite_graph_model $\endgroup$ – Joe Sep 7 '12 at 19:44
Edit: Wherever it says "vertex cover", read "dominating set".
Suppose that the sets are $S_1,\ldots,S_n$ and the elements are $x_1,\ldots,x_m$. For each set $S_i$ there will correspond a vertex $S_i$. For each element $x_j$ there will correspond $n$ vertices $x_j^{(1)},\ldots,x_j^{(n)}$. There is also an additional vertex $t$. Finally, assume wlog that the optimal solution for set cover is not $S_1,\ldots,S_n$ (this can be checked in polynomial time).
The instance of vertex cover is as follows. The vertex $t$ is connected to all of $S_1,\ldots,S_n$. Whenever $x_j \in S_i$, the vertex $S_i$ is connected to all of $x_j^{(1)},\ldots,x_j^{(n)}$. If there's a set cover of size $M$, then there is a vertex cover of size $M+1$ (we need to take the extra vertex $t$ so that all set vertices are covered). I believe that the converse should hold as well.
Try to work it out yourself, and if it doesn't work out, try to fix it and let us all know how.
-
$\begingroup$ I am afraid I did not get that. I tried to use a very simple example where the elements are 1, 2 and 3. The sets are {1, 2}, {3} and {2}. Then, for the set cover {{1, 2}, {3}}, we select the vertices corresponding to the selected sets and the vertex t. But from what I see, this still leaves the edge connecting the vertex ${2}$ with, say, $x_2^{(2)}$. Am I missing something here? By the way, I am very grateful for this answer of yours. From what I have seen, this reduction is not present on the internet. $\endgroup$ – Arani Aug 29 '12 at 21:45
-
1$\begingroup$ You're right, the reduction is actually to Dominating Set. Got my definition of Vertex Cover wrong! $\endgroup$ – Yuval Filmus Aug 30 '12 at 15:54
-
2$\begingroup$ There cannot be a nice reduction of this sort from Set Cover to Vertex Cover since the latter can be $2$-approximated, while the former cannot be approximate better than $\ln n$ (under some reasonable complexity assumption). $\endgroup$ – Yuval Filmus Aug 30 '12 at 15:56
-
$\begingroup$ Yes, I recognize that, but still there has to be a reduction since both are NP-Complete problems. Set cover is a more general problem than vertex cover, and that is why I am curious to know how the more general problem can be represented in terms of the other problem. $\endgroup$ – Arani Aug 31 '12 at 13:17
-
$\begingroup$ Since vertex cover is NP-complete, every NP language reduces to it. In particular, you can encode the execution of a Turing Machine verifying set cover as a SAT formula, then convert it into a vertex cover instance. You won't get anything pretty. $\endgroup$ – Yuval Filmus Aug 31 '12 at 16:33