Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms

DOI10.4230/LIPICS.IPEC.2017.7zbMATH Open1443.68121MaRDI QIDQ5111866FDOQ5111866

Édouard Bonnet, O-joung Kwon, Dániel Marx, Nick Brettell

Publication date: 27 May 2020

Recommendations

• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• Parameterized vertex deletion problems for hereditary graph classes with a block property
• On directed feedback vertex set parameterized by treewidth
• A Faster FPT Algorithm and a Smaller Kernel for Block Graph Vertex Deletion
• Parameterized and Exact Computation

zbMATH Keywords

treewidthfeedback vertex setfixed-parameter tractable algorithms

Mathematics Subject Classification ID

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)

Cites Work

• Title not available (Why is that?)
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Title not available (Why is that?)
• Title not available (Why is that?)
• Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth
• A \(c^k n\) 5-approximation algorithm for treewidth
• On the computational complexity of vertex integrity and component order connectivity
• An Exact Algorithm for Minimum Distortion Embedding
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• On the number of labeled graphs of bounded treewidth
• Parameterized Vertex Deletion Problems for Hereditary Graph Classes with a Block Property
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms

Cited In (4)

• Hitting minors on bounded treewidth graphs. III. Lower bounds
• Parameterized Complexity of Safe Set
• Optimality program in segment and string graphs
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms

This page was built for publication: Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms

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