Paper Info
Title
Diminishable Parameterized Problems And Strict Polynomial Kernelization
Abstract
Kernelization - a mathematical key concept for provably effective polynomial-time preprocessing of NP-hard problems - plays a central role in parameterized complexity and has triggered an extensive line of research. This is in part due to a lower bounds framework that allows to exclude polynomial-size kernels under the assumption of NP not subset of coNP/poly. In this paper we consider a restricted yet natural variant of kernelization, namely strict kernelization, where one is not allowed to increase the parameter of the reduced instance (the kernel) by more than an additive constant. Building on earlier work of Chen, Flum, and Muller [CiE 2009, Theory Comput. Syst. 2011], we underline the applicability of their framework by showing that a variety of fixed-parameter tractable problems, including graph problems and Turing machine computation problems, does not admit strict polynomial kernels under the assumption of P not equal NP, an assumption being weaker than the assumption of NP not subset of coNP/poly. Finally, we study an adaption of the framework to a relaxation of the notion of strict kernels, where in the latter one is not allowed to increase the parameter of the reduced instance by more than a constant times the input parameter.
Year
DOI
Venue
2020
10.3233/COM-180220
COMPUTABILITY-THE JOURNAL OF THE ASSOCIATION CIE
Keywords
DocType
Volume
NP-hard problems, parameterized complexity, kernelization lower bounds, polynomial-time data reduction, Exponential Time Hypothesis
Journal
9
Issue
ISSN
Citations 
1
2211-3568
0
PageRank 
References 
Authors
0.34
0
6
Name
Order
Citations
PageRank
Henning Fernau11646162.68
Till Fluschnik2267.14
Danny Hermelin379048.62
Andreas Krebs4218.20
Hendrik Molter55711.14
Rolf Niedermeier63465234.21