Take the Set Cover problem as an example. When we ask if there is a set of size k that covers all the elements, the problem is NP-complete. Now if we ask, for a given set $S$ of size $k$, if there exists another set that covers strictly more elements than $S$ does. Is this problem still NP-complete?

To be clearer, let's think about the Set Cover problem as an optimization problem: what is the maximum number of elements that can be covered by $k$ sets. The decision version is: are there $k$ sets that cover at least $m$ elements? (where $m$ is part of the input, and the version you were saying is simply the special case when $m=n$). Now the problem is, for $k$ given sets (as part of the input), does there exist $k$ other sets that cover strictly more elements than the $k$ given sets do.

  • $\begingroup$ duplicate of (cstheory.stackexchange.com/questions/41570/…) $\endgroup$ Sep 21 '18 at 15:42
  • $\begingroup$ What are your thoughts on the question? Have you tried proving NP-hardness? $\endgroup$ Sep 21 '18 at 15:49
  • $\begingroup$ @YuvalFilmus, I tried but without success. What I know is if it is required to give a witness when the answer is yes, then starting from a random solution and repeatedly asking if there's any other solution strictly better, we are able to reach the optimal solution in at most n steps (n being the number of elements in the set cover problem), which gives an answer to the set cover problem. However, if this is not required, I have no idea. $\endgroup$ Sep 21 '18 at 17:10
  • $\begingroup$ @ThinhD.Nguyen, yes, I posted there but no response so I reposed here. Should I delete that one? I'm not very familiar with the rules. Sorry. $\endgroup$ Sep 21 '18 at 17:13
  • $\begingroup$ @user2477759 Witnesses appear when proving that problems are in NP; your problem is in NP, since the witness is a better cover. The hard part is proving NP-hardness. Perhaps you should first make sure you have a solid understanding of how these proofs go. $\endgroup$ Sep 21 '18 at 17:21

Here is a reduction from Set Cover to your problem. Let $(\{S_1,\ldots,S_m\},k)$ be an instance of Set Cover, and let $U = S_1 \cup \cdots \cup S_m$. Let $x_1,\ldots,x_k$ be $k$ new elements, and consider the following instance of your problem:

  • The sets are $S_i \cup \{x_j\}$ for $i \in [m]$ and $j \in [k]$, together with the set $U$.
  • The given cover consists of $S_1 \cup \{x_j\}$ for $j \in [k-1]$ together with $U$.

The given cover covers all elements but $x_k$. There is a cover which covers more elements – that is, all elements – iff $U$ can be covered by at most $k$ sets from $S_1,\ldots,S_m$.


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.