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
lower boundsparameterized complexitygraph modification problemsinterdiction problemspolynomial-time data reductioncross-compositions
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)
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