Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems
Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems
复制标题
核化下界的分形及其在长度有界切割问题中的应用
DOI：
10.4230/lipics.icalp.2016.25
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
R. Niedermeier
中科院分区：
文献类型：
--
作者：
T. Fluschnik;D. Hermelin;A. Nichterlein;R. Niedermeier
Bodlaender等人的S[SIDMA2014]交叉合成技术是NP-Hard参数化问题中排除多项式大小问题核的一种流行方法。我们提出了一种利用基于三角形的分形结构来扩展交叉合成的适用范围的新技术。我们的技术使得证明一些涉及长度有界切割的问题的新的非多项式核结果成为可能。特别是，回答了Golovach和Thilikos提出的一个公开问题[离散方案。2011]，我们证明了，除非多项式层次结构出现崩溃，否则由组合$k$和$\ell$参数化的NP-难长度有界边割问题(删除至多$k$条边，使得得到的图没有长度小于$\ell$的$S$-$t$路径)没有多项式大小的问题核。我们的框架适用于基本问题的平面和有向变体，也适用于边和顶点删除问题。
关键词：固定参数可处理性；多项式核；核化；核下界；交叉合成；图形修改问题；分形学。
Bodlaender et al.'s [SIDMA 2014] cross-composition technique is a popular method for excluding polynomial-size problem kernels for NP-hard parameterized problems. We present a new technique exploiting triangle-based fractal structures for extending the range of applicability of cross-compositions. Our technique makes it possible to prove new no-polynomial-kernel results for a number of problems dealing with length-bounded cuts. In particular, answering an open question of Golovach and Thilikos [Discrete Optim. 2011], we show that, unless a collapse in the Polynomial Hierarchy occurs, the NP-hard Length-Bounded Edge-Cut problem (delete at most $k$ edges such that the resulting graph has no $s$-$t$ path of length shorter than $\ell$) parameterized by the combined $k$ and $\ell$ has no polynomial-size problem kernel. Our framework applies to planar as well as directed variants of the basic problems and also applies to both edge and vertex deletion problems.
Key words: Fixed-parameter tractability; polynomial kernels; kernelization; kernel lower bounds; cross-compositions; graph modification problems; fractals.
DOI：
10.4230/lipics.fsttcs.2015.448
发表时间：
2015
期刊：
ArXiv
影响因子：
--
作者：
T. Fluschnik;S. Kratsch;R. Niedermeier;M. Sorge
通讯作者：
M. Sorge