# Is this variant of set cover NP-complete?

Let's say we have a universe $U$ of $n$ elements and a collection $S$ of $m$ subsets of $U$, i.e., $S=\{S_1,\ldots,S_m\}$, and a positive integer $k$. If I ask "is there a set cover of $U$ of size $k$ or less", then this is NP-complete.

Now suppose that I add the following:

1. $|S_1| \gt |S_2| \gt \ldots \gt |S_m|$.

Is this still NP-complete?

I guess that, given 1., we know that the sets $S_i$ are all distinct and then the only cover for $U$ is $S$ but I am not sure about this.

• Can't you just make a reduction from the original set cover, adding as many dummy elements as it takes to satisfy the additional condition? Jan 29, 2017 at 2:50
• 1. Is $k$ part of the input, or is it fixed? 2. What's the context where you ran into this problem? Can you share anything about that?
– D.W.
Jan 29, 2017 at 3:12
• @quicksort But adding dummy elements to sets $S_i$ will make the union of $S_i$ is not $U$ right? According to the definition of set cover in Wikipedia, the union of $S_i$ is $U$.
– Zir
Jan 29, 2017 at 15:43
• @D.W. $k$ is part of the input. The context is that I am trying to find instances (or a variant) of set cover where the greedy algorithm (that selects the set which has the most uncovered elements) finds optimal solutions.
– Zir
Jan 29, 2017 at 15:44
• It doesn't matter. A reduction is just a function computable in logarithmic deterministic space (or polynomial deterministic time, depending on the definition you are using) that preserves language membership. The two problems you are reducing to and from could theoretically be not even remotely similar. If we need to change the universe, can definitely do so; we only need to be able to show that every instance of SET-COVER becomes some instance of your special case. Jan 29, 2017 at 15:53

## 1 Answer

As quicksort comments, you can convert any set cover instance to your special case by adding dummy elements. Take a large enough pool of dummy elements, and put all of it into a new set $S_1$. Then add subsets of $S_1$ to the other sets to satisfy your cardinality condition, taking care to leave some of them out. Every solution has to take $S_1$, and otherwise it just has to be a solution to the original problem.

This is of course not a formal reduction - this is left to the reader.

• Thanks. But adding dummy elements to sets $S_i$ will make the union of $S_i$ is not $U$ right? According to the definition of set cover in Wikipedia, the union of $S_i$ is $U$.
– Zir
Jan 29, 2017 at 15:43
• This can easily be fixed - details left to you. Jan 29, 2017 at 16:09