Bounded-cardinality bounded-frequency set cover: hardness of approximation

Question

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

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, here, and here 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?

Answer 1

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

Ignoring $k$,

• $\sup_k\{ a(\Delta,k) \}\leq \Delta$ (trivial).
• $\sup_k\{ a(4,k) \}\geq 2-\varepsilon$ (Holmerin, 2002)

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)

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

Answer 2

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

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

Answer 3

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, e.g. about 1.01-hardness in cubic graphs.

Answer 4

This does not quite answer your question, but perhaps it can help -- there is a paper [Dinur et al. 2004] which covers f > 2 (but seems not to fix k).