Diminishable Parameterized Problems and Strict Polynomial Kernelization
Diminishable Parameterized Problems and Strict Polynomial Kernelization
复制标题
DOI：
10.1007/978-3-319-94418-0_17
复制
发表时间：
2016-11
期刊：
影响因子：
--
通讯作者：
H. Fernau;T. Fluschnik;D. Hermelin;Andreas Krebs;Hendrik Molter;R. Niedermeier
中科院分区：
文献类型：
--
作者：
H. Fernau;T. Fluschnik;D. Hermelin;Andreas Krebs;Hendrik Molter;R. Niedermeier
核化是NP难问题的多项式时间预处理的一个数学关键概念，在参数化复杂性中起着核心作用，并引发了广泛的研究。这在一定程度上是由于一个下界框架，该框架允许在NP ≠ NP/poly的假设下排除多项式大小的内核。在本文中，我们考虑核化的一个限制，但自然的变种，即严格的核化，其中不允许增加参数的减少实例（内核）超过一个附加常数。基于Chen，Flum和Müller的早期工作[CiE 2009，Theory Comput. Syst.2011]，我们强调了他们的框架的适用性，通过显示各种固定参数的易处理的问题，包括图形问题和图灵机计算问题，不承认严格的多项式核的假设下，P= NP，一个假设是弱于假设的NP novacoNP/poly。最后，我们研究了一个适应的框架放松的概念，严格的内核，其中在后者是不允许增加参数的减少的实例超过一个常数倍的输入参数。
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⊈ 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 [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= NP, an assumption being weaker than the assumption of NP⊈ 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.