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

DOI10.4230/LIPICS.IPEC.2017.7MaRDI QIDQ5111866zbMATH OpenFDO

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

Publication date 27 May 2020

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)

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

Cites work

• scientific article; zbMATH DE number 6783431 (Why is no real title available?)
• scientific article; zbMATH DE number 6783432 (Why is no real title available?)
• A \(c^k n\) 5-approximation algorithm for treewidth
• An exact algorithm for minimum distortion embedding
• Deleting edges to restrict the size of an epidemic: a new application for treewidth
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• Graph theory
• Parameterized vertex deletion problems for hereditary graph classes with a block property
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(6)

• Hitting minors on bounded treewidth graphs. III. Lower bounds
• Optimality program in segment and string graphs
• Close relatives of feedback vertex set without single-exponential algorithms parameterized by treewidth
• Generalized feedback vertex set problems on bounded-treewidth graphs: chordality is the key to single-exponential parameterized algorithms
• Parameterized complexity of safe set
• Parameterized vertex deletion problems for hereditary graph classes with a block property

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)