A Cubic Kernel for Feedback Vertex Set

DOI10.1007/978-3-540-70918-3_28MaRDI QIDQ3590945zbMATH OpenOpenAlexFDO

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

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)

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

Cited in

(28)

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

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)