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.

Improve this question
$\endgroup$
6
  • 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
    Commented Jan 29, 2017 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. ♦
    Commented Jan 29, 2017 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
    Commented Jan 29, 2017 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
    Commented Jan 29, 2017 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
    Commented Jan 29, 2017 at 15:53

1 Answer 1

Reset to default
4
$\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.

Improve this answer
$\endgroup$
2
  • $\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
    Commented Jan 29, 2017 at 15:43
  • $\begingroup$ This can easily be fixed - details left to you. $\endgroup$
    – Yuval Filmus
    Commented Jan 29, 2017 at 16:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.