Near-Logarithmic Inapproximability of Parameterized Set Cover

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 $|\Gamma |$ 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 $\epsilon >0$ for which no deterministic algorithm solves this gap problem in time $f(k)|\Gamma {|}^{\epsilon k}$, for any computable function $f$. For every fixed $\alpha >0$, both hardness results hold even when $n=O((\log m{)}^{1+\alpha })$, with constants allowed to depend on $\alpha$. 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(|\Gamma {|}^{k-\delta })$ for every fixed $k\ge 2$ and $\delta >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 $\delta$.