<p>Using, as in James King's answer, the notation $a(\Delta,k)$ for the best possible polynomial time approximation of vertex cover in $k$-uniform hypergraphs of degree at most $\Delta$, we also have</p>

<p>(1) $a(\Delta,k) \leq \ln \Delta + O(1)$ </p>

<p>from the greedy approximation algorithm for set cover: vertex cover in hypergraphs of degree at most $\Delta$ is the same as the set cover problem with sets of size at most $\Delta$, for which the greedy algorithm has approximation ratio at most $H_\Delta$, where $H_n = 1 + 1/2 + \ldots 1/n \leq \ln n + O(1)$ is the harmonic function.</p>

<p>In <a href="http://portal.acm.org/citation.cfm?id=380752.380839">this paper</a> I show that </p>

<p>(2) $\sup_k \{ a(\Delta ,k) \} \geq \ln \Delta - O(\ln\ln \Delta)$ </p>

<p>unless $P=NP$, by changing the parameters in a reduction of Feige.</p>

CC BY-SA 4.0
2021-01-29T01:26:57.017Z
Does the randomized rounding method for set cover also achieve  ln$\delta$+O(1)?
Hao S
CC BY-SA 2.5
2010-12-22T02:43:04.507Z
2010-12-22T02:48:06.327Z
2010-12-22T02:48:06.327Z
Luca Trevisan
<p>Just in case you did not already find it; the most recent hardness result for bounded-degree Vertex Cover I found in recent searching is <a href="http://dx.doi.org/10.1016/j.tcs.2005.11.029">Chlebik &amp; Chlebikova</a>, e.g. about 1.01-hardness in cubic graphs.  </p>

CC BY-SA 2.5
2010-08-31T18:02:33.743Z
2010-08-31T18:02:33.743Z
daveagp
<p>This does not quite answer your question, but perhaps it can help -- there is a <a href="http://www.cs.huji.ac.il/~inapprox/papers/hvc-DGKR.ps">paper</a> [Dinur et al. 2004] which covers f > 2 (but seems not to fix k).</p>

CC BY-SA 2.5
2010-08-18T21:53:32.973Z
2010-08-18T21:53:32.973Z
Lev Reyzin
<p>Using the more common parameter notation $(\Delta,k)$ instead of $(k,f)$, this is equivalent to (and I think more commonly known as) the Vertex Cover problem in $k$-uniform hypergraphs of maximum degree $\Delta$.  To emphasize, for consistency with the literature I'm using $k$ where you use $f$, and $\Delta$ where you use $k$.</p>

<p>For any constant $\varepsilon > 0$, results ignoring $\Delta$ include</p>

<ul>
<li>$\sup_\Delta\{ a(\Delta,k) \}\leq k$ from general set cover.</li>
<li>$\sup_\Delta\{ a(\Delta,k) \}\geq k-1-\varepsilon$ <a href="http://www.cs.huji.ac.il/~inapprox/papers/hvc-DGKR.ps">(Dinur et al., 2004)</a>, as noted by Lev.</li>
<li>If the unique games conjecture is true, then $\sup_\Delta \{a(\Delta,k)\} \geq k-\varepsilon$, which is tight <a href="http://www.cs.tau.ac.il/~odedr/papers/vc_hard.pdf">(Khot &amp; Regev, 2008)</a>.</li>
</ul>

<p>Ignoring $k$, </p>

<ul>
<li>$\sup_k\{ a(\Delta,k) \}\leq \Delta$ (trivial).</li>
<li>$\sup_k\{ a(4,k) \}\geq 2-\varepsilon$ <a href="http://portal.acm.org/citation.cfm?id=509907.509986">(Holmerin, 2002)</a></li>
</ul>

<p>The only result I know that combines the two parameters is </p>

<ul>
<li>$a(\Delta,k) \leq k - (1-o(1))\left(\frac{k(k-1)\ln\ln\Delta}{\ln(\Delta)}\right)$ for fixed $k$, or $k$ growing slowly with $\Delta$ <a href="http://portal.acm.org/citation.cfm?id=587019">(Halperin, 2002)</a></li>
</ul>

<p>There is a connection between this problem and the (Weak) Independent Set problem, but I'm not exactly sure how they're related in terms of approximability.  I would recommend investigating this, perhaps starting here: <a href="http://www.hr.is/faculty/mmh/papers/DAM2.pdf">[PDF]</a>.</p>

CC BY-SA 2.5
2010-08-21T18:24:10.200Z
Thanks for the pointers, and apologies for using the somewhat confusing parameters. (I tried to be consistent with the use of the parameter $k$ in "minimum $k$-set cover", and I decided to follow the notation used in Vazirani's book.)
Jukka Suomela
CC BY-SA 2.5
2010-08-21T15:13:07.477Z
2010-08-21T15:13:07.477Z
James King
<p>Consider the <strong>minimum set cover</strong> problem with the following restrictions: each set contains at most $k$ elements and each element of the universe occurs in at most $f$ sets.</p>

<ul>
<li>Example: the case $k = 4$ and $f = 2$ is equivalent to the minimum vertex cover problem in graphs with maximum degree 4.</li>
</ul>

<p>Let $a(k,f) > 1$ be the largest value such that finding an $a(k,f)$-approximation of the minimum set cover problem with parameters $k$ and $f$ is NP-hard.</p>

<ul>
<li>Example: $a(4,2) \ge 1.0128$ (<a href="http://dx.doi.org/10.1007/3-540-48523-6_17">Berman &amp; Karpinski 1999</a>).</li>
</ul>

<p><strong>Question:</strong> Do we have a reference that summarises the strongest known lower bounds on $a(k,f)$? In particular, I'm interested in concrete values in the case that both $k$ and $f$ are small but $f > 2$.</p>

<hr>

<p>Restricted versions of the set cover problem are often convenient in reductions; typically there is some freedom in choosing the values of $k$ and $f$, and further information on $a(k,f)$ would help to choose the right values that provide the strongest hardness results. References <a href="http://www.nada.kth.se/~viggo/wwwcompendium/node10.html">here</a>, <a href="http://www.nada.kth.se/~viggo/wwwcompendium/node11.html">here</a>, and <a href="http://www.nada.kth.se/~viggo/wwwcompendium/node146.html">here</a> provide a starting point, but the information is somewhat outdated and fragmentary. I was wondering if there is a more complete and up-to-date source?</p>

CC BY-SA 2.5
2010-09-02T15:50:35.380Z
Thanks for the answers so far! Let's start a bounty and see if we can get more participation. For the sake of concreteness, I'll be happy to award the bounty if someone gives a pointer to a non-trivial lower bound on $a(3,3)$.
Jukka Suomela
CC BY-SA 2.5
2010-09-08T16:31:50.813Z
... and the bounty went to the answer that gave something that was closest to a lower bound on $a(3,3)$, but for the sake of fairness, I decided to accept the most thorough answer. Thanks to all; it seems that the case of $a(3,3)$ is indeed open.
Jukka Suomela
<cc.complexity-theory><reference-request><approximation-algorithms><set-cover><np-hardness>
Bounded-cardinality bounded-frequency set cover: hardness of approximation
Jukka Suomela
# Bounded-cardinality bounded-frequency set cover: hardness of approximation

(Asked by: username_0 on 2010-08-17)

Consider the **minimum set cover** problem with the following restrictions: each set contains at most $k$ elements and each element of the universe occurs in at most $f$ sets.

* Example: the case $k = 4$ and $f = 2$ is equivalent to the minimum vertex cover problem in graphs with maximum degree 4.

Let $a(k,f) > 1$ be the largest value such that finding an $a(k,f)$-approximation of the minimum set cover problem with parameters $k$ and $f$ is NP-hard.

* Example: $a(4,2) \ge 1.0128$ ([Berman & Karpinski 1999](http://dx.doi.org/10.1007/3-540-48523-6_17)).

**Question:** Do we have a reference that summarises the strongest known lower bounds on $a(k,f)$? In particular, I'm interested in concrete values in the case that both $k$ and $f$ are small but $f > 2$.

---

Restricted versions of the set cover problem are often convenient in reductions; typically there is some freedom in choosing the values of $k$ and $f$, and further information on $a(k,f)$ would help to choose the right values that provide the strongest hardness results. References [here](http://www.nada.kth.se/~viggo/wwwcompendium/node10.html), [here](http://www.nada.kth.se/~viggo/wwwcompendium/node11.html), and [here](http://www.nada.kth.se/~viggo/wwwcompendium/node146.html) provide a starting point, but the information is somewhat outdated and fragmentary. I was wondering if there is a more complete and up-to-date source?

**Tags:** cc.complexity-theory, reference-request, approximation-algorithms, set-cover, np-hardness

> **Comments:**
> **username_0**: Thanks for the answers so far! Let's start a bounty and see if we can get more participation. For the sake of concreteness, I'll be happy to award the bounty if someone gives a pointer to a non-trivial lower bound on $a(3,3)$.  
> **username_0**: ... and the bounty went to the answer that gave something that was closest to a lower bound on $a(3,3)$, but for the sake of fairness, I decided to accept the most thorough answer. Thanks to all; it seems that the case of $a(3,3)$ is indeed open.  

---

## 4 answers

### Answer by username_5 on 2010-08-21. Score: 15 | Accepted answer

Using the more common parameter notation $(\Delta,k)$ instead of $(k,f)$, this is equivalent to (and I think more commonly known as) the Vertex Cover problem in $k$-uniform hypergraphs of maximum degree $\Delta$. To emphasize, for consistency with the literature I'm using $k$ where you use $f$, and $\Delta$ where you use $k$.

For any constant $\varepsilon > 0$, results ignoring $\Delta$ include

* $\sup\_\Delta\{ a(\Delta,k) \}\leq k$ from general set cover.
* $\sup\_\Delta\{ a(\Delta,k) \}\geq k-1-\varepsilon$ [(Dinur et al., 2004)](http://www.cs.huji.ac.il/~inapprox/papers/hvc-DGKR.ps), as noted by Lev.
* If the unique games conjecture is true, then $\sup\_\Delta \{a(\Delta,k)\} \geq k-\varepsilon$, which is tight [(Khot & Regev, 2008)](http://www.cs.tau.ac.il/~odedr/papers/vc_hard.pdf).

Ignoring $k$,

* $\sup\_k\{ a(\Delta,k) \}\leq \Delta$ (trivial).
* $\sup\_k\{ a(4,k) \}\geq 2-\varepsilon$ [(Holmerin, 2002)](http://portal.acm.org/citation.cfm?id=509907.509986)

The only result I know that combines the two parameters is

* $a(\Delta,k) \leq k - (1-o(1))\left(\frac{k(k-1)\ln\ln\Delta}{\ln(\Delta)}\right)$ for fixed $k$, or $k$ growing slowly with $\Delta$ [(Halperin, 2002)](http://portal.acm.org/citation.cfm?id=587019)

There is a connection between this problem and the (Weak) Independent Set problem, but I'm not exactly sure how they're related in terms of approximability. I would recommend investigating this, perhaps starting here: [[PDF]](http://www.hr.is/faculty/mmh/papers/DAM2.pdf).

> **Comments:**
> **username_0**: Thanks for the pointers, and apologies for using the somewhat confusing parameters. (I tried to be consistent with the use of the parameter $k$ in "minimum $k$-set cover", and I decided to follow the notation used in Vazirani's book.)  

---

### Answer by username_1 on 2010-12-22. Score: 12

Using, as in username_5's answer, the notation $a(\Delta,k)$ for the best possible polynomial time approximation of vertex cover in $k$-uniform hypergraphs of degree at most $\Delta$, we also have

(1) $a(\Delta,k) \leq \ln \Delta + O(1)$

from the greedy approximation algorithm for set cover: vertex cover in hypergraphs of degree at most $\Delta$ is the same as the set cover problem with sets of size at most $\Delta$, for which the greedy algorithm has approximation ratio at most $H\_\Delta$, where $H\_n = 1 + 1/2 + \ldots 1/n \leq \ln n + O(1)$ is the harmonic function.

In [this paper](http://portal.acm.org/citation.cfm?id=380752.380839) I show that

(2) $\sup\_k \{ a(\Delta ,k) \} \geq \ln \Delta - O(\ln\ln \Delta)$

unless $P=NP$, by changing the parameters in a reduction of Feige.

> **Comments:**
> **username_2**: Does the randomized rounding method for set cover also achieve  ln$\delta$+O(1)?  

---

### Answer by username_3 on 2010-08-31. Score: 7

Just in case you did not already find it; the most recent hardness result for bounded-degree Vertex Cover I found in recent searching is [Chlebik & Chlebikova](http://dx.doi.org/10.1016/j.tcs.2005.11.029), e.g. about 1.01-hardness in cubic graphs.


---

### Answer by username_4 on 2010-08-18. Score: 6

This does not quite answer your question, but perhaps it can help -- there is a [paper](http://www.cs.huji.ac.il/~inapprox/papers/hvc-DGKR.ps) [Dinur et al. 2004] which covers f > 2 (but seems not to fix k).


---

