Fractals for kernelization lower bounds

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

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)

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

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

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)

Cites Work

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