HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Reduction from set cover problem to vertex cover problem

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
fromproblemvertexreductioncoverset

Problem

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?

Solution

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.

Context

StackExchange Computer Science Q#3354, answer score: 3

Revisions (0)

No revisions yet.