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$
$\endgroup$
3
-
$\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
Add a comment
|
$\begingroup$
$\endgroup$
7
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.
answered Aug 28 '12 at 22:28
-
$\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
