2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – quicksort Jan 29 '17 at 2:50
  • $\begingroup$ 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? $\endgroup$ – D.W. Jan 29 '17 at 3:12
  • $\begingroup$ @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$. $\endgroup$ – Zir Jan 29 '17 at 15:43
  • $\begingroup$ @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. $\endgroup$ – Zir Jan 29 '17 at 15:44
  • $\begingroup$ 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. $\endgroup$ – quicksort Jan 29 '17 at 15:53
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Zir Jan 29 '17 at 15:43
  • $\begingroup$ This can easily be fixed - details left to you. $\endgroup$ – Yuval Filmus Jan 29 '17 at 16:09

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.