Parameter hardness limits approximation of k-SetCover problems
Almost Optimal FPT Inapproximability for k-SetCover
Computational ComplexityData Structures and Algorithms
Summary
Covering problems ask how to pick the smallest number of groups to include all items. The paper finds nearly the best possible difficulty level for a version where you want to cover using exactly k groups. The authors improve older results by showing you can't efficiently get very close to the best solution when k is a parameter. They use clever logical formulas and hash functions to prove this hardness without relying on previous assumptions. This helps clarify how hard it really is to approximate these problems quickly.
What this means in practice
- •For algorithm designers: Rule out possibility of fast algorithms that closely approximate k-SetCover for large k based on parameterized complexity assumptions.
- •For complexity theorists: Establish tighter inapproximability bounds to guide research on parameterized optimization problems.
A theory result. No direct application yet.
Authors
Venkatesan Guruswami, Xuandi Ren
Abstract
We show that $\bigl(\frac{\log n}{\log\log n}\bigr)$-approximate parameterized $k$-SetCover is W[1]-hard, and has no $n^{o(k/\log k)}$-time algorithms under ETH. This improves upon the previous best factors $\bigl(\frac{\log n}{\log\log n}\bigr)^{1/k}$ in (Lin, 2019) and $(\log n)^{1/\operatorname{poly}(k)}$ in (Karthik, Laekhanukit, and Manurangsi, 2019). Here $k$ is the yes-case guarantee and $n$ is the number of candidate sets. While the best approximation ratio is still $O(\log n)$ via the greedy algorithm, closing this $1/k$ gap in the exponent has been a longstanding open problem; we remove this loss via a simple direct reduction. The construction is self-contained and does not rely on the parameterized inapproximability hypothesis (PIH). Starting with sparse parameterized 2-CSP instances (Karthik, Marx, Pilipczuk, and Souza, 2024), we build a monotone CNF formula, which is equivalent to a SetCover instance. To obtain a $k$-versus-$h$ gap, the reduction enumerates all hash functions from $Σ$ to $[2h]$ and all unsatisfiable 2-CSP instances on the same constraint graph with alphabet $[2h]$. For each such instance, it asks for a certificate that the hashed label pairs are not all contained in that instance. Perfect hashing makes this enumeration efficient for $h=\log n/\log\log n$.