[2202.04377] Constant Approximating Parameterized $k$-SetCover is W[2]-hard
source link: https://arxiv.org/abs/2202.04377
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
[Submitted on 9 Feb 2022 (v1), last revised 23 Oct 2022 (this version, v2)]
Constant Approximating Parameterized k-SetCover is W[2]-hard
In this paper, we prove that it is W[2]-hard to approximate k-SetCover within any constant ratio. Our proof is built upon the recently developed threshold graph composition technique. We propose a strong notion of threshold graphs and use a new composition method to prove this result. Our technique could also be applied to rule out polynomial time o\left(\frac{\log n}{\log \log n}\right) ratio approximation algorithms for the non-parameterized k-SetCover problem with k as small as O\left(\frac{\log n}{\log \log n}\right)^3, assuming W[1]\neqFPT. We highlight that our proof does not depend on the well-known PCP theorem, and only involves simple combinatorial objects.
| Subjects: | Data Structures and Algorithms (cs.DS); Computational Complexity (cs.CC) |
| ACM classes: | F.2.2 |
| Cite as: | arXiv:2202.04377 [cs.DS] |
| (or arXiv:2202.04377v2 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2202.04377 |
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK