Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
DOI10.1007/s00453-019-00579-4zbMath1430.68179arXiv1704.06757OpenAlexW2940485869WikidataQ115606750 ScholiaQ115606750MaRDI QIDQ2272595
O-joung Kwon, Dániel Marx, Nick Brettell, Édouard Bonnet
Publication date: 10 September 2019
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1704.06757
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
Related Items (5)
Cites Work
- On the complexity of some colorful problems parameterized by treewidth
- On the computational complexity of vertex integrity and component order connectivity
- Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Efficient Computation of Representative Families with Applications in Parameterized and Exact Algorithms
- Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property
- Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth
- Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal
- A Complexity Dichotomy for Hitting Small Planar Minors Parameterized by Treewidth
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
- Slightly Superexponential Parameterized Problems
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
