Kernelization for feedback vertex set via elimination distance to a forest

DOI10.1016/j.dam.2023.12.016OpenAlexW4390151090MaRDI QIDQ6153475

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

zbMATH Keywords

feedback vertex setkernelizationelimination distance

Mathematics Subject Classification ID

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

Cites Work

• Structural parameterizations of undirected feedback vertex set: FPT algorithms and kernelization
• The complexity ecology of parameters: An illustration using bounded max leaf number
• A cubic kernel for feedback vertex set and loop cutset
• On problems without polynomial kernels
• A better heuristic for orthogonal graph drawings
• Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity
• Faster deterministic \textsc{Feedback Vertex Set}
• Improved analysis of highest-degree branching for feedback vertex set
• Polynomial kernels for hitting forbidden minors under structural parameterizations
• Towards tight(er) bounds for the excluded grid theorem
• Polynomial kernels for vertex cover parameterized by small degree modulators
• How much does a treedepth modulator help to obtain polynomial kernels beyond sparse graphs?
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Fixed-parameter tractable distances to sparse graph classes
• Crown structures for vertex cover kernelization
• Crown reductions for the minimum weighted vertex cover problem
• Preprocessing to reduce the search space: antler structures for feedback vertex set
• Vertex Cover: Further Observations and Further Improvements
• Hitting Forbidden Minors: Approximation and Kernelization
• The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel
• Feedback Vertex Set on Graphs of Low Cliquewidth
• Kernelization: New Upper and Lower Bound Techniques
• Vertex packings: Structural properties and algorithms
• Reducibility among Combinatorial Problems
• Bridge-Depth Characterizes which Minor-Closed Structural Parameterizations of Vertex Cover Admit a Polynomial Kernel
• Smaller Parameters for Vertex Cover Kernelization
• Detecting Feedback Vertex Sets of Size k in O*(2.7^k) Time
• Losing Treewidth by Separating Subsets
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses
• Parameterized Algorithms
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• Graph-Theoretic Concepts in Computer Science
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Vertex deletion parameterized by elimination distance and even less
• Unnamed Item
• Unnamed Item
• Unnamed Item

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