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.
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:
With Noga Alon and Muli Safra, we showed how to use the Raz-Safra/Arora-Sudan PCP to get a better constant $c$ in the hardness factor $c\log n$.
http://people.csail.mit.edu/dmoshkov/papers/k-restrictions/k-rest-full.ps
Feige showed how to get the optimal hardness factor $(1-\epsilon)\ln n$, assuming $NP\not\subseteq DTIME(n^{\log\log n})$.
http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf
I recently published a note on how to adapt Feige's reduction to an NP-hardness result (i.e., a result based on $P\neq NP$), assuming a plausible conjecture about PCPs (A conjecture I call "The Projection Games Conjecture" - a specialization of the 1993 "Sliding Scale Conjecture" to projection games).
http://eccc.hpi-web.de/report/2011/112/ (I later found out that the reduction gives an optimal tradeoff between $\epsilon$ and the reduction blow-up).
-
$\begingroup$ What is the weakest separation assumption that will still yield a $(1-\epsilon)\log n$ hardness ? $\endgroup$ – Suresh Venkat Oct 1 '11 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$ – Edith Elkind Oct 2 '11 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$ – Dana Moshkovitz Oct 2 '11 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$ – Dana Moshkovitz Oct 2 '11 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$ – Edith Elkind Oct 2 '11 at 16:20
