zbMATH — the first resource for mathematics

Fractals for kernelization lower bounds, with an application to length-bounded cut problems. (English) Zbl 1388.68111
Chatzigiannakis, Ioannis (ed.) et al., 43rd international colloquium on automata, languages, and programming, ICALP 2016, Rome, Italy, July 12–15, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-013-2). LIPIcs – Leibniz International Proceedings in Informatics 55, Article 25, 14 p. (2016).
Summary: H. L. Bodlaender et al.’s [SIAM J. Discrete Math. 28, No. 1, 277–305 (2014; Zbl 1295.05222)] 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 P. A. Golovach and D. M. Thilikos [Discrete Optim. 8, No. 1, 72–86 (2011; Zbl 1248.90071)], we show that, unless \(\mathrm{NP}\subseteq\mathrm{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 \(\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.
For the entire collection see [Zbl 1351.68012].

68Q25 Analysis of algorithms and problem complexity
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI