I know that set cover problem is NP-complete. We are given a universe $U$ (a set) of $n$ elements and a collection $S$ of $m$ sets whose union equals the universe and an integer $k$. The set cover problem is to identify a sub-collection of $S$ of size $k$ or less whose union equals the universe?

Now if I remove or less, and ask instead that is there a sub-collection of $S$ of size $k$ whose union equals the universe? Is this still NP-complete?

Here, of course, $k<m$.

My answer is that the problem is still NP-complete. From the initial problem we simply keep the same instance and we find a set cover of size $s\leqslant k$ then the modified problem has a set cover of size $k$ if $s=k$.

Any help?

  • $\begingroup$ For any instance, there is a Set Cover of size $k$ if and only if there is a set cover of size at most $k$. (Because, given any set cover of size less than $k$, you can add arbitrary sets to it to obtain a set cover of size $k$.) So, the "or less" makes no difference at all - the problem is exactly the same with or without it. The special-purpose reductions in the answer below are not necessary. $\endgroup$ – Neal Young Aug 27 '18 at 12:40

Yes, it remains NP-complete, even under the restriction that all subsets of a specific size $s$ (which translates to immediately requiring that $k = n / s$.

For example, for $k = n / 3$, 3-dimensional matching can be directly reduced to your problem.

  • $\begingroup$ @det YW, cool you ended up finding it yourself :). $\endgroup$ – aelguindy Nov 6 '16 at 16:39

I have found an answer for my question in [1]. The problem I am interested in, called in [1] MINIMUM COVER, is NP-complete by reduction from 3-EXACT COVER.

The 3-EXACT COVER is defined as [1]: Given a family $F=\{S_1,\ldots,S_n\}$ of $n$ subsets of $S=\{u_1,\ldots,u_{3m}\}$, each of cardinality three, is there a subfamily of $m$ subsets that covers $S$?

The 3-EXACT COVER is NP-complete [1].

The MINIMUM COVER is defined as [1]: Given a family $F=\{S_1,\ldots,S_n\}$ of subsets of a finite set $U$, and an integer $k\leqslant n$, is there a subfamily $C$ of $F$ containing $k$ sets such that $\bigcup\limits_{S_j\in C}S_j=U$?

As stated in [1], the 3-EXACT COVER is just the special case of MINIMUM COVER in which $|S_j|=3$ for $j=1,\ldots,n$, and $k=\frac{1}{3}|U|$. Consequently, any instance of 3-EXACT COVER can be trivially transformed into an instance of MINIMUM COVER. ...

[1] C. H. Papadimitriou and K. Steiglitz. Combinatorial Optimization. Algorithms and Complexity. Dover Publications, 1998. First published in 1982 by Prentice-Hall.


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.