26
$\begingroup$

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.

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?

$\endgroup$
  • $\begingroup$ 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)$. $\endgroup$ – Jukka Suomela Sep 2 '10 at 15:50
  • $\begingroup$ ... 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. $\endgroup$ – Jukka Suomela Sep 8 '10 at 16:31
15
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Jukka Suomela Aug 21 '10 at 18:24
12
$\begingroup$

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.

$\endgroup$
7
+50
$\begingroup$

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.

$\endgroup$
6
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.