Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
From MaRDI portal
Publication:4962217
DOI10.1145/2797140zbMath1398.68245arXiv1207.0835OpenAlexW1838629830MaRDI QIDQ4962217
Alexander Langer, Ignasi Sau, Somnath Sikdar, Felix Reidl, Christophe Paul, Eun Jung Kim, Peter Rossmanith
Publication date: 30 October 2018
Published in: ACM Transactions on Algorithms, Automata, Languages, and Programming (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1207.0835
algorithmic meta-theoremsparameterized complexitysparse graphsgraph minorslinear kernelshitting minorssingle-exponential algorithms
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph minors (05C83) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (56)
Compactors for parameterized counting problems ⋮ Characterising bounded expansion by neighbourhood complexity ⋮ Paths to Trees and Cacti ⋮ A Retrospective on (Meta) Kernelization ⋮ Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets ⋮ Uniform Kernelization Complexity of Hitting Forbidden Minors ⋮ A \(13k\)-kernel for planar feedback vertex set via region decomposition ⋮ A Structural Approach to Kernels for ILPs: Treewidth and Total Unimodularity ⋮ Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property ⋮ Towards constant-factor approximation for chordal/distance-hereditary vertex deletion ⋮ Kernelization using structural parameters on sparse graph classes ⋮ Editing to a Planar Graph of Given Degrees ⋮ Bivariate Complexity Analysis of Almost Forest Deletion ⋮ Distance from triviality 2.0: hybrid parameterizations ⋮ Lower bounds for protrusion replacement by counting equivalence classes ⋮ Sparse obstructions for minor-covering parameters ⋮ A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion ⋮ An FPT algorithm and a polynomial kernel for linear rankwidth-1 vertex deletion ⋮ On kernelization and approximation for the vector connectivity problem ⋮ A polynomial kernel for block graph deletion ⋮ Quick but odd growth of cacti ⋮ Finite Integer Index of Pathwidth and Treewidth ⋮ Meta-kernelization using well-structured modulators ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ Bivariate complexity analysis of \textsc{Almost Forest Deletion} ⋮ Polynomial Kernel for Interval Vertex Deletion ⋮ Hitting Minors on Bounded Treewidth Graphs. IV. An Optimal Algorithm ⋮ Planarizing graphs and their drawings by vertex splitting ⋮ Small vertex cover helps in fixed-parameter tractability of graph deletion problems over data streams ⋮ A high-order norm-product regularized multiple kernel learning framework for kernel optimization ⋮ Polynomial kernels for hitting forbidden minors under structural parameterizations ⋮ Unnamed Item ⋮ A naive algorithm for feedback vertex set ⋮ Hitting Minors on Bounded Treewidth Graphs. I. General Upper Bounds ⋮ First-Order Model-Checking in Random Graphs and Complex Networks ⋮ Explicit linear kernels for packing problems ⋮ Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes ⋮ Polynomial Kernels for Hitting Forbidden Minors under Structural Parameterizations. ⋮ On the Parameterized Complexity of Clique Elimination Distance ⋮ A linear kernel for planar red-blue dominating set ⋮ Paths to trees and cacti ⋮ Unnamed Item ⋮ On the number of labeled graphs of bounded treewidth ⋮ Editing to a planar graph of given degrees ⋮ A polynomial kernel for distance-hereditary vertex deletion ⋮ Unnamed Item ⋮ A single-exponential FPT algorithm for the \(K_4\)-\textsc{minor cover} problem ⋮ Bidimensionality and Kernels ⋮ Modification to Planarity is Fixed Parameter Tractable ⋮ Structural sparsity of complex networks: bounded expansion in random models and real-world graphs ⋮ Unnamed Item ⋮ Lossy Kernels for Connected Dominating Set on Sparse Graphs ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs? ⋮ How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs ⋮ Twin-width and polynomial kernels ⋮ Hitting Topological Minor Models in Planar Graphs is Fixed Parameter Tractable
This page was built for publication: Linear Kernels and Single-Exponential Algorithms Via Protrusion Decompositions
