Constant Approximating Parameterized k -SETCOVER is W[2]-hard
Bingkai Lin, Xuandi Ren, Yican Sun, Xiuhan Wang · Society for Industrial and Applied Mathematics eBooks · 2023
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 ratio approximation algorithms for the non-parameterized k-SETCOVER problem with k as small as , assuming W[1] ≠ FPT. We highlight that our proof does not depend on the well-known PCP theorem, and only involves simple combinatorial objects.