Kernelization for feedback vertex set via elimination distance to a forest
From MaRDI portal
Publication:6153475
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
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.7k) 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