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$ This seems quite ill-defined to me. It looks like for any choice of a subcollection, there is a cost function $f(A_1 \ldots A_k)$. But what does "not known in advance" mean ? NP-hardness does not make sense in an online setting. On the other hand, if the function f is known beforehand, is it fixed or part of the input ? In the latter case, specializing $f(A_1 \ldots A_k)=k$ reduces it back to the usual covering problem. In the former, some instances will be trivial (take f=0 for example). Do you want to determine which properties of f will make it hard ? $\endgroup$
    – Arnaud
    Oct 7 '13 at 11:02
  • $\begingroup$ @Arnaud Thanks! I have re-defined the problem. Hope it is clear now. $\endgroup$
    – Fnatic
    Oct 7 '13 at 11:26

Yes, it is still NP-Hard. First, note that the unweighted set cover problem is also NP-hard. We can reduce the unweighted set cover problem $(U,S)$ to your problem as follows.

First, constructing a new ground set $U'=U\cup V\cup \{x\}$, where $|V|=|U|=n$. Then, extend each set $s_i\in S$ by setting $s_i'=s_i\cup V_i$ where $V_i$ is some subset of $V$ containing $n-|s_i|$ elements, so that each $s_i'$ has $n$ elements. Finally add one last set $s_0'=V\cup \{x\}$ so that $S'=\{s_0',s_1',\ldots,s_m'\}$.

The solution to your version of the set cover problem with $S'$ and $U'$ will return $s_0'$ along with an optimal solution to the original unweighted set cover problem -- since all the sets in $S'$ are of equal size, then the weighting scheme won't matter.


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.