arXiv preprint ·
Almost Optimal FPT Inapproximability for k-SetCover
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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$.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computational Complexity
Weighted Quantum Signal Processing: Low-Depth Polynomial Approximation with Applications to Kolmogorov-Arnold Networks
Human Language Shapes the Emerging Physical Reasoning in Large Language Models
A lower bound for $\langle 3,2,m \rangle$ matrix multiplication
Systematic Data Structure Lower Bounds via the Query-with-Sketch Model
Algorithmic Collusion and the Complexity of Information-Value-Free Equilibria
Get the few papers worth your time in Computational Complexity every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.