2016/11/11 by Henning Fernau, Till Fluschnik, Fernau, Henning +9 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1611.03739
openalex publication_date 2016/11/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
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 \nsubseteq 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 Müller [Theory Comput. Syst. 2011] and developing a general and remarkably simple framework, we show that a variety of FPT problems does not admit strict polynomial kernels under the weaker assumption of P ≠ NP. In particular, we show that various (multicolored) graph problems and Turing machine computation problems do not admit strict polynomial kernels unless P = NP. To this end, a key concept we use are diminishable problems; these are parameterized problems that allow to decrease the parameter of the input instance by at least one in polynomial time, thereby outputting an equivalent problem instance. Finally, we study a relaxation of the notion of strict kernels and reveal its limitations.