论文标题
常量近似参数化$ k $ -setCover为w [2] - hard
Constant Approximating Parameterized $k$-SetCover is W[2]-hard
论文作者
论文摘要
在本文中，我们证明在任何恒定比率内都是w [2] - 近似k检测。我们的证明是基于最近开发的阈值图组成技术。我们提出了阈值图的强烈概念，并使用新的组成方法来证明这一结果。我们的技术也可以应用于排除多项式时间$ o \ left（\ frac {\ log n} {\ log \ log \ log n} \ right）$比率近似算法，用于非参数化的k-ketcover问题，带有$ k $的$ k $ at $ o \ frac \ weft（\ frac \ weft} \ log n}假设W [1] $ \ neq $ fpt。我们强调说，我们的证明不取决于众所周知的PCP定理，而仅涉及简单的组合对象。
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]$\neq$FPT. We highlight that our proof does not depend on the well-known PCP theorem, and only involves simple combinatorial objects.
