Consider a variation of the set cover problem in which we only have to cover some certain amount of elements. Is this problem still NP-hard? I guess yes? Is there a good reference?

  • 1
    $\begingroup$ If we have to cover at least $rn$ elements, we can just add $n/r$ elements not in any set to any instance to reduce to the regular set cover problem. Also, the set cover problem is NP-hard to approximate up to any constant, so even if you are told that there exists a solution covering all elements with at most $k$ sets, it's hard to cover $rn$ elements with at most $k$ sets (consider an instance with $1 / r$ copies of the same instance). $\endgroup$ – Antti Röyskö Feb 17 at 3:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.