Metraipolis › archive › dc_af41eaf6de02
Almost Optimal FPT Inapproximability for k-SetCover — arXiv:2609.19685
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.19685
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-10T05:44:47.942Z
- SHA-256 of the archived text
7fc5bd8f1230c99ddd0fa6d10bd2b7acaf5c90446ebc2f71456d1b19257bea8a- Stable URL of this page
https://metraipolis.com/documento/dc_af41eaf6de02
How to cite
Almost Optimal FPT Inapproximability for k-SetCover — arXiv:2609.19685 — arXiv (en), https://arxiv.org/abs/2609.19685 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_af41eaf6de02 (Metraipolis archive dc_af41eaf6de02, sha256 7fc5bd8f1230c99ddd0fa6d10bd2b7acaf5c90446ebc2f71456d1b19257bea8a)
BibTeX
@misc{dcaf41eaf6de02,
title = {Almost Optimal FPT Inapproximability for k-SetCover — arXiv:2609.19685},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.19685},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_af41eaf6de02; sha256 7fc5bd8f1230c99ddd0fa6d10bd2b7acaf5c90446ebc2f71456d1b19257bea8a},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.19685. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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 $\Sigma$ 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$.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-18 in cs.DS).
Categorie arXiv: Computational Complexity (cs.CC) ; Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2609.19685 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T05:08:06.586Z dalla pagina https://arxiv.org/catchup/cs.DS/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).