2026-08-17T09:43:17Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6304 2024-03-06T10:37:40Z ddc:004 open_access

Fractals for Kernelization Lower Bounds, With an Application to Length-Bounded Cut Problems Fluschnik, Till Hermelin, Danny Nichterlein, André Niedermeier, Rolf Parameterized complexity polynomial-time data reduction cross-compositions lower bounds graph modification problems interdiction problems 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Till Fluschnik and Danny Hermelin and André Nichterlein and Rolf Niedermeier 2016 Is Part Of LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2016.25 urn:nbn:de:0030-drops-63049 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.25 eng https://creativecommons.org/licenses/by/3.0/legalcode