Fluschnik, Till
[Verfasser:in];
Hermelin, Danny
[Verfasser:in];
Nichterlein, André
[Verfasser:in];
Niedermeier, Rolf
[Verfasser:in]
;
Till Fluschnik and Danny Hermelin and André Nichterlein and Rolf Niedermeier
[Mitwirkende:r]
Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems
Anmerkungen:
Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
Beschreibung:
Bodlaender et al.'s [Bodlaender/Jansen/Kratsch,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 [Golovach/Thilikos,2011], we show that, unless NP subseteq coNP/poly, 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.