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

Bingkai Lin, Xuandi Ren, Yican Sun +1

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 techniq…