4
$\begingroup$

In the set cover (SC) problem we are given a universe $U$ (a set) of $n$ elements and a collection $S$ of $m$ sets whose union equals the universe. The set cover problem is to identify the smallest sub-collection of $S$ whose union equals the universe.

If I add the constraint that $m=n$ to SC, is this new problem still NP-hard?

My attempt is as follows:

To construct an instance of the new problem we do:

  1. If $n=m$, then we are done.
  2. If $n>m$, then we simply add $n-m$ dummy sets to the collection $S$ and we are done.
  3. If $n<m$, then ... (I am stuck). But I think since the union of the $m$ sets is $U$ then we must have that $S$ contains redundant sets. Is this OK?
$\endgroup$
6
$\begingroup$

Yes, it is still NP-complete. If you have an instance with $n < m$, then you can pad $U$ with $m - n + 1$ new elements and add new subset containing only the new elements. The original instance has a solution of size $s$ if and only the padded instance has a solution of size $s + 1$. The reduction is obviously polynomial time.

$\endgroup$
  • $\begingroup$ Thank you. My logic in the third point is it correct? $\endgroup$ – Ribz Nov 2 '16 at 15:15
  • $\begingroup$ @det I don't know what you mean by "sets". $\endgroup$ – aelguindy Nov 2 '16 at 15:45
  • $\begingroup$ For example if I had $U=\{1,2,3\}$ and $S=\{S_1,S_2,S_3,S_4,S_5\}$ (i.e., $n=3$ and $m=5$. By definition of the SC problem $S_1\cup S_2\cup S_3\cup S_4\cup S_5=U$ then I thought that we must have some sets from $S$ that are redundant. $\endgroup$ – Ribz Nov 2 '16 at 15:49
  • $\begingroup$ Redundant in the sense that there is a subcollection of distinct m subsets that cover the universe, but not redundant as in we can throw them away and the optimum won't change. $\endgroup$ – aelguindy Nov 2 '16 at 15:57

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.