The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel

DOI10.1007/11847250_18zbMath1154.68421OpenAlexW2128317498MaRDI QIDQ3499737

Kevin Burrage, Shev mac, Michael R. Fellows, Frances A. Rosamond, Michael A. Langston, Vladimir Estivill-Castro

Publication date: 3 June 2008

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11847250_18

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (30)

Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies ⋮ Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds ⋮ A \(13k\)-kernel for planar feedback vertex set via region decomposition ⋮ Kernelization – Preprocessing with a Guarantee ⋮ Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms ⋮ Preprocessing to reduce the search space: antler structures for feedback vertex set ⋮ Approximation and Kernelization for Chordal Vertex Deletion ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ A Linear Kernel for Planar Feedback Vertex Set ⋮ Kernelization for feedback vertex set via elimination distance to a forest ⋮ A randomized polynomial kernel for subset feedback vertex set ⋮ Unnamed Item ⋮ Kernel bounds for disjoint cycles and disjoint paths ⋮ Quadratic kernelization for convex recoloring of trees ⋮ Confronting intractability via parameters ⋮ Exploring the Kernelization Borders for Hitting Cycles ⋮ Subset Feedback Vertex Set Is Fixed-Parameter Tractable ⋮ A cubic kernel for feedback vertex set and loop cutset ⋮ Tree Deletion Set Has a Polynomial Kernel but No $\text{OPT}^\mathcal{O}(1)$ Approximation) ⋮ On the small cycle transversal of planar graphs ⋮ Faster deterministic \textsc{Feedback Vertex Set} ⋮ A Quartic Kernel for Pathwidth-One Vertex Deletion ⋮ Hitting Forbidden Minors: Approximation and Kernelization ⋮ The complexity ecology of parameters: An illustration using bounded max leaf number ⋮ Improved analysis of highest-degree branching for feedback vertex set ⋮ On problems without polynomial kernels ⋮ Unnamed Item ⋮ Unnamed Item

This page was built for publication: The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel