Problem Detail: 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:
- If $n=m$, then we are done.
- If $n>m$, then we simply add $n-m$ dummy sets to the collection $S$ and we are done.
- 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?
Asked By : Riebuoz
Answered By : aelguindy
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/65403 3.2K people like this
