# Is the set cover problem NP-complete when the cardinality of the collection of sets is equal to the cardinality of the universe?

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?

## 1 Answer

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.

• Thank you. My logic in the third point is it correct? – Ribz Nov 2 '16 at 15:15
• @det I don't know what you mean by "sets". – aelguindy Nov 2 '16 at 15:45
• 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. – Ribz Nov 2 '16 at 15:49
• 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. – aelguindy Nov 2 '16 at 15:57