3
$\begingroup$

I'm not familiar with complexity theory at all so please correct me if I make any incorrect statements.

I am wondering what is the hard case of set cover? My understanding of NP-hardness is that it describes a worse case scenario. In other words, if I am only considering set cover for say the case that the number of subsets is less than the number of elements in the ground set (or vice versa), can I say that this case falls under a 'hard' or 'easy' case of set cover.

Moreover, in looking at the work by Dinur and Steurer 2013 , they say it is NP-hard to approximate set cover within a factor of $(1−\epsilon)ln (n)$, where $n$ is the size of the universe, but they don't mention the size of the collection of subsets (denote $m$), does this imply that this inapproximability result should hold for any $m$, regardless of it $m < n$ or $m > n$?

$\endgroup$
2
$\begingroup$

When you have a result like "It is NP-hard to approximate X within ..." or say "X is NP-complete", it means that there is an infinite family of instances of X that are hard. This is what worst case intractability means.

In your example, the hardness of approximation result holds for the set cover problem, meaning that there is an infinite family of instances of set cover that are hard to approximate.

At this point, you might put further constraints on a problem in the form of "suppose every set satisfies this property" or whatever, but this is then a different problem, i.e., you are narrowing down on the instances that you care about. If you have a statement that says "set cover with your favorite property is NP-hard to approximate", it means that there is (still!) an infinite family of instances of this problem that remain hard.

$\endgroup$
  • $\begingroup$ Thank you! As a follow up question, I was reading this result from Feige 1998, which proves an approximation result by reducing some other problem to set cover. He states that all the instances of set cover that he constructs have number of subsets less than number of ground set elements. Based on what you said, it is that his result still hold for all instances of set cover? $\endgroup$ – M. Qin Apr 10 at 15:54
  • $\begingroup$ I can't see the result of Feige at the moment, but if a hardness result holds for "set cover with property X", there is an infinite family of instances of the mentioned problem that are hard. Consequently, every instance of the mentioned problem is an instance of general set cover, so the result holds for that too. But no, it doesn't mean that every instance is hard. Does it make sense? $\endgroup$ – Juho Apr 10 at 16:00

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.