<p>Yes, the number of sets m in a set-cover instance is polynomial in the number of elements.</p>
<p>By the way -- the state of the art hardness results for Set-Cover are:</p>
<ul>
<li><p>With Noga Alon and Muli Safra, we showed how to use the Raz-Safra/Arora-Sudan PCP to get a better constant <span class="math-container">$c$</span> in the hardness factor <span class="math-container">$c\log n$</span>.</p>
<p><a href="http://people.csail.mit.edu/dmoshkov/papers/k-restrictions/k-rest-full.ps" rel="nofollow noreferrer">http://people.csail.mit.edu/dmoshkov/papers/k-restrictions/k-rest-full.ps</a></p>
</li>
<li><p>Feige showed how to get the optimal hardness factor <span class="math-container">$(1-\epsilon)\ln n$</span>, assuming <span class="math-container">$NP\not\subseteq DTIME(n^{\log\log n})$</span>.</p>
<p><a href="http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf" rel="nofollow noreferrer">http://www.cs.duke.edu/courses/spring07/cps296.2/papers/p634-feige.pdf</a></p>
</li>
<li><p>I recently published a note on how to adapt Feige's reduction to an NP-hardness result (i.e., a result based on <span class="math-container">$P\neq NP$</span>), assuming a plausible conjecture about PCPs (A conjecture I call &quot;The Projection Games Conjecture&quot; - a specialization of the 1993 &quot;Sliding Scale Conjecture&quot; to projection games).</p>
<p><a href="http://eccc.hpi-web.de/report/2011/112/" rel="nofollow noreferrer">http://eccc.hpi-web.de/report/2011/112/</a>
(I later found out that the reduction gives an optimal tradeoff between <span class="math-container">$\epsilon$</span> and the reduction blow-up).</p>
</li>
</ul>

CC BY-SA 3.0
2011-10-01T21:00:04.300Z
What is the weakest separation assumption that will still yield a $(1-\epsilon)\log n$ hardness ?
Suresh Venkat
CC BY-SA 3.0
2011-10-02T06:35:18.090Z
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?
Edith Elkind
CC BY-SA 3.0
2011-10-02T12:57:14.710Z
@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.
Dana Moshkovitz
CC BY-SA 3.0
2011-10-02T13:00:36.873Z
@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.
Dana Moshkovitz
CC BY-SA 3.0
2011-10-02T16:20:59.490Z
@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...
Edith Elkind
CC BY-SA 3.0
2011-10-02T21:32:48.843Z
@lostinjungle: If I came up with a reduction with the parameters you described, I wouldn't have called the instance constructed "poly-size" (even though it can be interesting in the case a better reduction was not known). It's just a matter of standards/conventions. There's nothing deep here.
Dana Moshkovitz
CC BY-SA 3.0
2011-10-02T22:34:01.777Z
@DanaMoshkovitz: Yes, sorry. I should have said $\ln n$.
Suresh Venkat
CC BY-SA 3.0
2011-10-01T16:30:46.343Z
2011-10-17T19:27:23.057Z
2020-06-17T09:38:08.363Z
Dana Moshkovitz
<p>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. </p>

<cc.complexity-theory><approximation-hardness><set-cover>
Inapproximability of set cover: can I assume m=poly(n)?
Edith Elkind
# Inapproximability of set cover: can I assume m=poly(n)?

(Asked by: username_0 on 2011-10-01)

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.

**Tags:** cc.complexity-theory, approximation-hardness, set-cover


---

## 1 answers

### Answer by username_1 on 2011-10-01. Score: 18 | Accepted answer

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).

> **Comments:**
> **username_2**: What is the weakest separation assumption that will still yield a $(1-\epsilon)\log n$ hardness ?  
> **username_0**: 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?  
> **username_1**: @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.  
> **username_1**: @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.  
> **username_0**: @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...  
> **username_1**: @lostinjungle: If I came up with a reduction with the parameters you described, I wouldn't have called the instance constructed "poly-size" (even though it can be interesting in the case a better reduction was not known). It's just a matter of standards/conventions. There's nothing deep here.  
> **username_2**: @DanaMoshkovitz: Yes, sorry. I should have said $\ln n$.  

---

