Linear-time kernelization for feedback vertex set

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

Yoichi Iwata

Publication date: 27 May 2020

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

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

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)

Cited In (22)

• A parameterized complexity view on collapsing \(k\)-cores
• Multi-Budgeted Directed Cuts
• Exact algorithms for restricted subset feedback vertex set in chordal and split graphs
• Title not available (Why is that?)
• 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
• Kernelization for feedback vertex set via elimination distance to a forest
• Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs
• Title not available (Why is that?)
• 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
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Title not available (Why is that?)
• Space-efficient graph kernelizations
• 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
• Euler Digraphs
• Title not available (Why is that?)
• 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)