Fractals for kernelization lower bounds

DOI10.1137/16M1088740MaRDI QIDQ4609787zbMATH OpenOpenAlexFDO

Authors Till Fluschnik, Danny Hermelin, André Nichterlein, Rolf Niedermeier

Publication date 26 March 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

lower boundsparameterized complexitygraph modification problemsinterdiction problemspolynomial-time data reductioncross-compositions

Mathematics Subject Classification ID

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

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.

Recommendations

• Fractals for kernelization lower bounds, with an application to length-bounded cut problems
• Kernelization Lower Bounds by Cross-Composition
• Cross-composition: a new technique for kernelization lower bounds
• scientific article; zbMATH DE number 7053262
• Lower bounds for kernelization

Cites work

• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• (Meta) Kernelization
• A partial k-arboretum of graphs with bounded treewidth
• A refined complexity analysis of finding the most vital edges for undirected shortest paths
• Advice classes of parametrized tractability
• Clique Cover and Graph Separation
• Diameter increase caused by edge deletion
• Face covers and the genus problem for apex graphs
• Fixed-parameter algorithms for DAG partitioning
• Fundamentals of parameterized complexity
• Graph theory
• Incompressibility through Colors and IDs
• Infeasibility of instance compression and succinct PCPs for NP
• Interdiction problems on planar graphs
• Kernel bounds for disjoint cycles and disjoint paths
• Kernelization Lower Bounds by Cross-Composition
• Kernelization for cycle transversal problems
• Length-bounded cuts and flows
• Lossy kernelization
• Lower bounds based on the exponential time hypothesis
• New limits to classical and quantum instance compression
• Node-and edge-deletion NP-complete problems
• On problems without polynomial kernels
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• On the small cycle transversal of planar graphs
• Parameterized algorithms
• Parameterized approximation via fidelity preserving transformations
• Parameterized complexity of firefighting
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Parametrized complexity of length-bounded cuts and multi-cuts
• Parametrized complexity theory.
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Recent developments in kernelization: a survey
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• Some simplified NP-complete graph problems
• The complexity of finding maximum disjoint paths with length constraints
• The design of approximation algorithms
• The k most vital arcs in the shortest path problem
• The parameterized complexity of the minimum shared edges problem
• Two-page book embeddings of 4-planar graphs

Cited in

(12)

• Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges
• A more fine-grained complexity analysis of finding the most vital edges for undirected shortest paths
• The complexity of finding small separators in temporal graphs
• scientific article; zbMATH DE number 7765394 (Why is no real title available?)
• A survey of parameterized algorithms and the complexity of edge modification
• Lower bounds on kernelization
• Elements of efficient data reduction: fractals, diminishers, weights and neighborhoods
• On polynomial-time combinatorial algorithms for maximum \(L\)-bounded flow
• Fractals for kernelization lower bounds, with an application to length-bounded cut problems
• Length-bounded cuts: proper interval graphs and structural parameters
• scientific article; zbMATH DE number 7758343 (Why is no real title available?)
• The complexity of finding small separators in temporal graphs

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)