FRACTALS FOR KERNELIZATION LOWER BOUNDS

The 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 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., 8 (2011), pp. 77-86], we show that, unless NP subset of coNP / poly, the NP-hard LENGTH-BOUNDED EDGE-CUT (LBEC) 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. Along the way, we show that LBEC remains NP-hard on planar graphs, a result which we believe is interesting in its own right.