1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Oh, I misunderstood the task while working on it... I thought, we should find the cover not for $\mathbb{U}$, but for $\cup S$, then, if we throw away any element from S, we can not say anything about default problem, the set we should cover is changed. Yes, you are right, how could I be so careless... :) $\endgroup$ – gukoff Apr 19 '13 at 10:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.