In the Set Covering problem, we are given a ground set $U$ and a collection $S$ of subsets of $U$, where each subset is associated with a non-negative cost, the Set Cover problem asks to find a minimum cost subcollection of $S$ that covers all elements in $U$. It is well known that the Set Covering problem is NP-hard.

Now my question is: Is the problem of finding a subcollection $A$ of $S$ that covers all elements in $U$ with minimum $\sum\limits_{i=1}^{|A|} |s_i| \cdot i$ (Here $|A|$ denotes the number of subsets in subcollection $A$, and $|s_i|$ denotes the number of elements in subset $s_i$. A is sorted in non-increasing order of $|s_i|$) still NP-hard. If so, how to prove it? Thanks in advance.

  • $\begingroup$ You will probably have to make the statement of your "modified set covering" problem more precise. For example, what is the cost of $A$ if I choose all three of $A$, $B$, and $C$? Exactly how is the cost of a set determined? $\endgroup$ – user642796 Oct 7 '13 at 10:24
  • $\begingroup$ @ArthurFischer Thanks! I have revised the title and statement of the problem. Hope this time it is clear. $\endgroup$ – Fnatic Oct 7 '13 at 11:24

You can prove a problem is NP-hard by showing a polynomial time reduction of a known NP-hard problem to your problem. Observe that SET COVER can be reduced to your problem by padding out all the sets with duplicate elements so that they all have the same cardinality, which can be done in polynomial time. This is a polynomial many-one reduction from SET COVER to your problem, which proves that your problem is NP-hard.

  • $\begingroup$ Thank you very much, Kyle Jones. I think that is the right answer. $\endgroup$ – Fnatic Oct 8 '13 at 7:32

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.