Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems
Till Fluschnik (TU Berlin)
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. Roughly speaking, our new technique combines the advantages of serial and parallel composition. 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 l) parameterized by the combination of k and l 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.
This is joint work with Danny Hermelin, André Nichterlein, and Rolf Niedermeier.
Back to the research colloquium site.