Linear-time kernelization for feedback vertex set

DOI10.4230/LIPICS.ICALP.2017.68zbMATH Open1441.68188MaRDI QIDQ5111399FDOQ5111399

Authors Yoichi Iwata 

Publication date 27 May 2020

Full work available at URL https://arxiv.org/abs/1608.01463

zbMATH Keywords

kernelizationFPT algorithmspath packinghalf-integrality

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• A cubic kernel for feedback vertex set and loop cutset
• A Cubic Kernel for Feedback Vertex Set
• A quadratic kernel for feedback vertex set
• A 4k^2 kernel for feedback vertex set
• A Linear Kernel for Planar Feedback Vertex Set

Cited In (22)

• A parameterized complexity view on collapsing \(k\)-cores
• A parameterized complexity view on collapsing \(k\)-cores
• Exact algorithms for restricted subset feedback vertex set in chordal and split graphs
• Title not available (Why is no real title available?)
• Kernelization for feedback vertex set via elimination distance to a forest
• An improved FPT algorithm for independent feedback vertex set
• Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies
• Multi-budgeted directed cuts
• Multi-budgeted directed cuts
• Kernelization for feedback vertex set via elimination distance to a forest
• Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs
• Improved analysis of highest-degree branching for feedback vertex set
• A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion
• Linear Vertex-kernels for Several Dense Ranking r -Constraint Satisfaction Problems
• Euler digraphs
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Space-efficient graph kernelizations
• Computing kernels in parallel: lower and upper bounds
• Crossing Paths with Hans Bodlaender: A Personal View on Cross-Composition for Sparsification Lower Bounds
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• The PACE 2018 parameterized algorithms and computational experiments challenge: the third iteration
• A randomized polynomial kernel for subset feedback vertex set

This page was built for publication: Linear-time kernelization for feedback vertex set

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