Fractals for Kernelization Lower Bounds
| Autor: | Till Fluschnik, André Nichterlein, Danny Hermelin, Rolf Niedermeier |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
FOS: Computer and information sciences
Discrete Mathematics (cs.DM) General Mathematics F.1.3 F.2.2 G.2.2 Parameterized complexity 0102 computer and information sciences Computational Complexity (cs.CC) 01 natural sciences 68Q17 68Q25 68W40 68R10 Combinatorics symbols.namesake Computer Science - Data Structures and Algorithms Data Structures and Algorithms (cs.DS) 0101 mathematics Mathematics Discrete mathematics 010102 general mathematics Composition (combinatorics) Planar graph Computer Science - Computational Complexity Range (mathematics) 010201 computation theory & mathematics Kernelization Path (graph theory) symbols Graph (abstract data type) Kernel (category theory) Computer Science - Discrete Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | SIAM Journal on Discrete Mathematics. 32:656-681 |
| ISSN: | 1095-7146 0895-4801 |
| DOI: | 10.1137/16m1088740 |
| Popis: | 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. Comment: An extended abstract appeared in Proc. of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). A full version will appear in SIAM Journal on Discrete Mathematics (SIDMA) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|