Problem Detail: In the set cover problem we want to find in the $mathbb{S} subset 2^mathbb{U}$ the subset ${s_i}_{1..k}$, such that $cup s_i = mathbb{U}$ for given $K$, where $k le K$. But how to reduce the set cover problem to the set covering decision problem (determining whether is there such cover or not)? The same with problems like a TSP is always easy enough: we exclude some elements, check if the needed condition is still met and know already, are these elements needed or not. But it doesn’t work here and I am stuck. I would be appreciated if you could give me some hints for this problem.
Asked By : Harold
Answered By : Shaull
There are two approaches for this: The “hands on” way: first, find the minimal $k$ for which there is a set cover, by repeatedly calling an oracle for the decision problem (you can even do a binary search, but it isn’t necessary). Once you have the minimal $k$, choose a set $s_1in S$, and check if there is a set cover of size $k$ in $Ssetminus{s_1}$. If there is, you don’t need $s_1$, so throw it away. If there isn’t, remove $s_1$ from $U$, and repeat the process with $k-1$, until you have the set cover, which will be minimal. The more theoretical approach is as follows. Since SET-COVER is NP-complete, there is a reduction from it to SAT, and a reduction from SAT to SET-COVER. If you examine the standard reductions (i.e. the Cook-Levin theorem, and a textbook reduction for $SATle_p SET-COVER$), you will see that both reductions are Levin reductions, which means that not only they are reductions, but they also preserve witnesses. That is, given a solution to the output of the reduction, you can generate from it a solution to the input. Now you can proceed as follows. Given an instance for SET-COVER, find the minimal $k$ as before, and then reduce the problem with this $k$ to SAT. Now, if you have an oracle for the decision problem, you can reduce SAT to the SET-COVER, so you can also solve SAT using this oracle. For SAT we know how to find a solution using an oracle (just try bit-by-bit), so you can find a witness, and from this generate a witness for SET-COVER. The latter works with any NP-complete problem.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/11403
