Kernelization for feedback vertex set via elimination distance to a forest

DOI10.1016/J.DAM.2023.12.016OpenAlexW4390151090MaRDI QIDQ6153475FDOQ6153475

Authors: David Dekker, Bart M. P. Jansen 

Publication date: 14 February 2024

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2023.12.016

Recommendations

• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
• Structural Parameterizations of Feedback Vertex Set
• A Cubic Kernel for Feedback Vertex Set
• A quadratic kernel for feedback vertex set

zbMATH Keywords

kernelizationfeedback vertex setelimination distance

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Reducibility among combinatorial problems
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• On problems without polynomial kernels
• A \(4k^2\) kernel for feedback vertex set
• Feedback vertex set on graphs of low cliquewidth
• Parameterized algorithms
• Vertex packings: Structural properties and algorithms
• Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses
• A better heuristic for orthogonal graph drawings
• Hitting forbidden minors: approximation and kernelization
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• A cubic kernel for feedback vertex set and loop cutset
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Faster deterministic \textsc{Feedback Vertex Set}
• Crown structures for vertex cover kernelization
• Crown reductions for the minimum weighted vertex cover problem
• Vertex cover: Further observations and further improvements
• Graph-Theoretic Concepts in Computer Science
• Kernelization: new upper and lower bound techniques
• Smaller parameters for vertex cover kernelization
• The complexity ecology of parameters: An illustration using bounded max leaf number
• Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Linear-time kernelization for feedback vertex set
• Improved analysis of highest-degree branching for feedback vertex set
• Towards tight(er) bounds for the excluded grid theorem
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Fixed-parameter tractable distances to sparse graph classes
• Vertex deletion parameterized by elimination distance and even less
• Polynomial kernels for vertex cover parameterized by small degree modulators
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• Detecting Feedback Vertex Sets of Size k in O*(2.7^k) Time
• Polynomial kernels for hitting forbidden minors under structural parameterizations
• Losing Treewidth by Separating Subsets
• Structural parameterizations with modulator oblivion
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel

This page was built for publication: Kernelization for feedback vertex set via elimination distance to a forest

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