8

[2202.04377] Constant Approximating Parameterized $k$-SetCover is W[2]-hard

 2 years ago
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.
neoserver,ios ssh client

[Submitted on 9 Feb 2022 (v1), last revised 23 Oct 2022 (this version, v2)]

Constant Approximating Parameterized k-SetCover is W[2]-hard

Download PDF

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

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK