# How hard is it to decide if there exists a strict improvement of a given solution of an NP-complete problem?

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.

• duplicate of (cstheory.stackexchange.com/questions/41570/…) – Thinh D. Nguyen Sep 21 '18 at 15:42
• What are your thoughts on the question? Have you tried proving NP-hardness? – Yuval Filmus Sep 21 '18 at 15:49
• @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. – user2477759 Sep 21 '18 at 17:10
• @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. – user2477759 Sep 21 '18 at 17:13
• @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. – Yuval Filmus 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$$.