Polynomial kernels collapse the W-hierarchy
Preprint
Abstract
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 results are also extended to assumed exponential kernels for problems in the class FPT. In particular, we establish a close relationship between polynomial (and exponential) kernelizability and the existence of sub-exponential time algorithms for a spectrum of circuit satisfiability problems in FPT. To the best of our knowledge, this is the first work that connects hardness for polynomial kernelizability of FPT problems to parameterized intractability. Our work also offers some new insights into the class FPT.Keywords
All Related Versions
This publication has 11 references indexed in Scilit:
- Special Issue on Parameterized Complexity of Discrete OptimizationDiscrete Optimization, 2011
- On problems without polynomial kernelsJournal of Computer and System Sciences, 2009
- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel SizeSIAM Journal on Computing, 2007
- Strong computational lower bounds via parameterized complexityJournal of Computer and System Sciences, 2006
- On the existence of subexponential parameterized algorithmsJournal of Computer and System Sciences, 2003
- Which Problems Have Strongly Exponential Complexity?Journal of Computer and System Sciences, 2001
- Vertex Cover: Further Observations and Further ImprovementsJournal of Algorithms, 2001
- On the Complexity of k-SATJournal of Computer and System Sciences, 2001
- On Fixed-Parameter Tractability and Approximability of NP Optimization ProblemsJournal of Computer and System Sciences, 1997
- Fixed-parameter tractability and completeness IV: On completeness for W[P] and PSPACE analoguesAnnals of Pure and Applied Logic, 1995