Set cover problem hard to approximate within near logarithmic factor
Near-Logarithmic Inapproximability of Parameterized Set Cover
Computational Complexity
Summary
The set cover problem asks how to cover a universe of items using as few sets as possible. The authors show it is very hard to find a close approximation of the smallest number of sets when looking for a cover of size k. They prove that even allowing some slack, no fast algorithm can reliably distinguish small covers from much larger covers. This holds true even with some strong complexity assumptions, meaning that efficient algorithms can only get so close to the best solution. Their findings set limits on how well algorithms can perform on this problem.
What this means in practice
- •For algorithm designers: Understand the fundamental limits when developing fast approximation algorithms for set cover parameterized by cover size k.
- •For complexity theorists: Use the hardness results to guide the search for efficient algorithms by ruling out certain approximation and runtime combinations.
A theory result. No direct application yet.
Authors
Bingkai Lin, Xin Zheng
Abstract
We study the approximability of \textnormal{\textsc{Set Cover}} parameterized by the target cover size $k$. Let $n$ be the universe size, $m$ the number of available sets, and $|Γ|$ the explicit input length. We prove that, for some absolute constant $c>0$, distinguishing \[ \operatorname{opt}(Γ)\le k \quad\text{from}\quad \operatorname{opt}(Γ)>k\cdot\frac{c\log n}{k^2\log\log n} \] is $\mathsf{W[1]}$-hard. Assuming the Exponential Time Hypothesis, there is also an absolute constant $\varepsilon>0$ for which no deterministic algorithm solves this gap problem in time $f(k)|Γ|^{\varepsilon k}$, for any computable function $f$. For every fixed $α>0$, both hardness results hold even when $n=O((\log m)^{1+α})$, with constants allowed to depend on $α$. For fixed $k$, the gap is within an $O_k(\log\log n)$ factor of the greedy algorithm's guarantee. Under the Strong Exponential Time Hypothesis, we further rule out $o(\log n/\log\log n)$ approximation in time $O(|Γ|^{k-δ})$ for every fixed $k\ge 2$ and $δ>0$. Thus a near-logarithmic hardness factor persists even when the exponent is reduced from exhaustive search by only a fixed constant. The constant in this SETH hardness factor may depend on $k$ and $δ$.