CS Peer Talks

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

  • Xuandi Ren, Turing Class
  • Time: 2022-03-07 10:00
  • Host: Turing Class Research Committee
  • Venue: Online Talk


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 graph and use a new composition method to prove this result. Our technique could also be applied to rule out polynomial time o(log n/loglog n) ratio approximation algorithms for the non-parameterized k-SetCover problem, assuming W[1]≠FPT. We highlight that our proof does not depend on the well-known PCP theorem, and only involves simple combinatorial objects. Furthermore, our reduction results in a k-SetCover instance with k as small as O(log^2 nloglog n).



Xuandi Ren is a senior undergraduate in Turing Class, Peking University. His research interests lie in theoretical computer science, especially in Computational Complexity and Hardness of Approximation.


  • Admission