Near-Logarithmic Inapproximability of Parameterized Set Cover

Abstract

In the $\gamma$-gap $k$-SetCover problem, we are given a family $\mathcal{S}$ over a universe $U$, and the goal is to distinguish between the case where $\mathcal{S}$ contains $k$ sets covering $U$, and the case where at least $\gamma k$ sets in $\mathcal{S}$ are needed to cover $U$. We show that, for every $k^{\Omega (k^2)}\le \rho \le n^{O(1)}$, it is W[1]-hard to approximate $k$-SetCover within ratio $\Omega \left(\frac{\log \rho }{k^2\log \log \rho }\right)$ on instances with $n$ sets and universe size at most $\rho \log n$. We also show that under the randomized $k$-OV Hypothesis, there is no bounded-error randomized $f(k)n^{o(k)}$-time $o\left(\frac{\log N}{\log \log N}\right)$-approximation algorithm for $k$-SetCover. These results improve on the previous $(\log n{)}^{1/O(k)}$-inapproximability. For fixed $k$, this matches the polynomial-time $(\ln \rho +O(1))$-approximation up to a $\log \log \rho$ factor. We further establish a connection between small universes and large approximation gaps. We show that for every $1\le \gamma \le \min \{\frac{\log u}{\log \log N},\frac{\log u}{k^2\log \log u}\}$, exact $k$-SetCover with universe size $u^{\Theta (1/\gamma )}$ is equivalent to $\gamma$-gap $k$-SetCover with universe size $u$ under randomized Turing reductions. This suggests a barrier to proving superconstant-gap W[2]-hardness: such a result would also make exact $k$-SetCover with universe size $n^{o(1)}$ W[2]-hard under randomized FPT Turing reductions. Finally, we analyze the VC dimensions of the set systems produced by our reduction. Write $d$ and $d^{\ast }$ for the primal and dual VC dimensions respectively. We show that for $\gamma =o(\frac{\log N}{\log \log N})$, $\gamma$-gap $k$-SetCover is W[1]-hard even when $d=O(k^2\gamma \log (k\gamma ))$ and $d^{\ast }=O(k\gamma )$. The bound for $d^{\ast }$ matches the $O(d^{\ast }\log k)$-approximation algorithm up to a $k\log k$ factor.