Polynomial kernels collapse the W-hierarchy

Liang Ding, Abdul Samad, Xingran Xue +2

We prove that, for many parameterized problems in the class FPT, the existence of polynomial kernels implies the collapse of the W-hierarchy (i.e., W[P] = FPT). The collapsing resu…