A Cubic Kernel for Feedback Vertex Set

DOI10.1007/978-3-540-70918-3_28zbMATH Open1186.68217OpenAlexW2113924317MaRDI QIDQ3590945FDOQ3590945

Authors: Hans L. Bodlaender 

Publication date: 3 September 2007

Published in: STACS 2007 (Search for Journal in Brave)

Full work available at URL: https://dspace.library.uu.nl/handle/1874/22185

Recommendations

• A cubic kernel for feedback vertex set and loop cutset
• A quadratic kernel for feedback vertex set
• A \(4k^2\) kernel for feedback vertex set
• An improved kernel for the undirected planar feedback vertex set problem
• A Linear Kernel for Planar Feedback Vertex Set

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Cited In (28)

• A Linear Kernel for Planar Feedback Vertex Set
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• Iterative Compression for Exactly Solving NP-Hard Minimization Problems
• Parameterized graph cleaning problems
• Vertex cover kernelization revisited: upper and lower bounds for a refined parameter
• Kernelization for feedback vertex set via elimination distance to a forest
• Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
• On problems without polynomial kernels
• On the small cycle transversal of planar graphs
• A \(4k^2\) kernel for feedback vertex set
• Compression via matroids: a randomized polynomial kernel for odd cycle transversal
• Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
• A quartic kernel for pathwidth-one vertex deletion
• Kernel bounds for disjoint cycles and disjoint paths
• On the parameterized complexity of reconfiguration problems
• Feedback vertex sets in cubic multigraphs
• Lower bounds on kernelization
• A cubic kernel for feedback vertex set and loop cutset
• Subexponential parameterized algorithms
• Confronting intractability via parameters
• Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
• Exploring the kernelization borders for hitting cycles
• A Problem Kernelization for Graph Packing
• A quadratic kernel for feedback vertex set
• A randomized polynomial kernel for subset feedback vertex set
• The complexity ecology of parameters: An illustration using bounded max leaf number
• Hitting forbidden minors: approximation and kernelization
• Linear-time kernelization for feedback vertex set

This page was built for publication: A Cubic Kernel for Feedback Vertex Set

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3590945)