Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems

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.