Fractals for Kernelization Lower Bounds

DOI10.1137/16M1088740zbMATH Open1388.68112arXiv1512.00333OpenAlexW2962863824MaRDI QIDQ4609787

Author name not available (Why is that?)

Publication date: 26 March 2018

Published in: (Search for Journal in Brave)

Abstract: 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. 2011], we show that, unless NP $subseteq$ 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 $ell$) parameterized by the combination of $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. Along the way, we show that LBEC remains NP-hard on planar graphs, a result which we believe is interesting in its own right.

Full work available at URL: https://arxiv.org/abs/1512.00333

zbMATH Keywords

No records found.

Mathematics Subject Classification ID

No records found.

This page was built for publication: Fractals for Kernelization Lower Bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4609787)