[Solved]: Set cover problem and the existence of such cover

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_1\in S$, and check if there is a set cover of size $k$ in $S\setminus\{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 $SAT\le_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