Fractals for Kernelization Lower Bounds

DOI10.1137/16M1088740zbMath1388.68112arXiv1512.00333OpenAlexW2962863824MaRDI QIDQ4609787

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

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)

Related Items (9)

Length-bounded cuts: proper interval graphs and structural parameters ⋮ Preventing small \(\mathbf{(s,t)} \)-cuts by protecting edges ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ On Polynomial-Time Combinatorial Algorithms for Maximum $L$-Bounded Flow ⋮ Unnamed Item ⋮ Unnamed Item ⋮ 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 ⋮ The complexity of finding small separators in temporal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Fundamentals of parameterized complexity
• Kernelization for cycle transversal problems
• Paths of bounded length and their cuts: parameterized complexity and algorithms
• Fixed-parameter algorithms for DAG partitioning
• On the small cycle transversal of planar graphs
• Infeasibility of instance compression and succinct PCPs for NP
• Kernel bounds for disjoint cycles and disjoint paths
• Advice classes of parametrized tractability
• Interdiction problems on planar graphs
• On problems without polynomial kernels
• The k most vital arcs in the shortest path problem
• Some simplified NP-complete graph problems
• A partial k-arboretum of graphs with bounded treewidth
• Face covers and the genus problem for apex graphs
• On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems
• Parameterized complexity of firefighting
• Parametrized complexity theory.
• Parameterized Approximation via Fidelity Preserving Transformations
• Clique Cover and Graph Separation
• A Refined Complexity Analysis of Finding the Most Vital Edges for Undirected Shortest Paths
• Parametrized Complexity of Length-Bounded Cuts and Multi-cuts
• Two-Page Book Embeddings of 4-Planar Graphs
• The Design of Approximation Algorithms
• Length-bounded cuts and flows
• New Limits to Classical and Quantum Instance Compression
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Incompressibility through Colors and IDs
• Diameter increase caused by edge deletion
• The complexity of finding maximum disjoint paths with length constraints
• Lossy kernelization
• Kernelization Lower Bounds by Cross-Composition
• (Meta) Kernelization
• The Parameterized Complexity of the Minimum Shared Edges Problem
• Node-and edge-deletion NP-complete problems
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• Parameterized Algorithms

This page was built for publication: Fractals for Kernelization Lower Bounds