I am trying to show that a certain problem is inapproximable by a reduction from set cover. My reduction transforms an instance with ground set of size $n$ and $m$ sets into an instance of my problem where a certain parameter $r$ is of size $O(n+m)$. I can then show that an instance of set cover where the cover size is s corresponds to an instance of my problem where the size of the optimal solution is $2s$ (or something like this), and vice versa. I would like to invoke Raz-Safra to conclude that my problem is inapproximable up to a factor of $c \log{r}$, for some constant $c$. This would work fine if I could assume that $m$ is bounded by a fixed polynomial of $n$. Does anyone know if it is kosher to assume this? This is certainly true for the family of instances used in the standard NP-hardness proof for set cover, but I am not sure if this remains the case for the kind of PCP reductions employed by Raz and Safra.


1 Answer 1


Yes, the number of sets m in a set-cover instance is polynomial in the number of elements.

By the way -- the state of the art hardness results for Set-Cover are:

  • $\begingroup$ What is the weakest separation assumption that will still yield a $(1-\epsilon)\log n$ hardness ? $\endgroup$ Oct 1, 2011 at 21:00
  • $\begingroup$ Dana, thanks for your answer! A follow-up question, if you do not mind: is this a "stupid" question, i.e., are there any high-level considerations that imply m=poly(n), or is it the case that one actually has to know the Raz-Safra hardness proof to answer my question? $\endgroup$ Oct 2, 2011 at 6:35
  • 1
    $\begingroup$ @Suresh: I assume you mean $(1-\epsilon)\ln n$. The assumption of Feige ($NP\not\subseteq DTIME(n^{\log\log n})$) and my assumption ("The Projection Games Conjecture") are incomparable. I believe that my assumption would be proved in the foreseeable future. $\endgroup$ Oct 2, 2011 at 12:57
  • $\begingroup$ @lostinjungle: If m hadn't have been polynomial in n, you couldn't have considered the reduction a "poly-time reduction". The particular reason that a Raz-Safra/Arora-Sudan PCP yields m=poly(n) is that there is a set per a PCP variable/constraint + and assignment to them, and the number of variables and constraints, as well as the size of the alphabet are polynomial, and the number of queries is constant. $\endgroup$ Oct 2, 2011 at 13:00
  • 1
    $\begingroup$ @DanaMoshkovitz: Thanks! I am not sure I understand your first claim, though. What's wrong with the following (hypothetical) reduction: I start with an instance of (say) Vertex Cover with $k$ vertices and create an instance of Set Cover with $m = k^3$ sets and ground set of size $n$, where $n$ is the solution to $n^{\log n} = m$? This definitely works in poly-time. Admittedly, I have never seen a reduction like this, but it does not seem logically impossible. Or am I wrong? Of course, my original question has already been answered, so feel free to ignore this one. I am just curious... $\endgroup$ Oct 2, 2011 at 16:20

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.