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, 2012 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$– JoeSep 7, 2012 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$– JoeSep 7, 2012 at 19:44
Add a comment
|
2 Answers
$\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, 2012 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$– AraniAug 29, 2012 at 21:45
-
1$\begingroup$ You're right, the reduction is actually to Dominating Set. Got my definition of Vertex Cover wrong! $\endgroup$ Aug 30, 2012 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$ Aug 30, 2012 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$– AraniAug 31, 2012 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$ Aug 31, 2012 at 16:33
$\begingroup$
$\endgroup$
If you make a set of subsets out of the edges of a graph and solve the set cover problem, youll have solved the vertex cover problem. This is true for any graph. If you take a set of subsets, a. You may not be able to make it into graph. 2. even if you did the vertex cover might not be the set cover.
