Kernelization for feedback vertex set via elimination distance to a forest

DOI10.1016/J.DAM.2023.12.016MaRDI QIDQ6153475zbMATH OpenOpenAlexFDO

Authors David Dekker, Bart M. P. Jansen

Publication date 14 February 2024

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

Copyright license Creative Commons Attribution 4.0 International

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

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)

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

Cites work

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

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)