Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable

DOI10.1145/2700209zbMath1398.68222arXiv1205.1271OpenAlexW1846185267MaRDI QIDQ4962189

Mohammataghi Hajiaghayi, Marek Cygan, Dániel Marx, Rajesh Chitnis

Publication date: 30 October 2018

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1205.1271

zbMATH Keywords

directed graphsparameterized algorithmssubset feedback vertex setimportant separators

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (18)

Towards a polynomial kernel for directed feedback vertex set ⋮ Kernels for deletion to classes of acyclic digraphs ⋮ Integer programming in parameterized complexity: five miniatures ⋮ Parameterized complexity of weighted multicut in trees ⋮ Parameterized complexity of multicut in weighted trees ⋮ A parameterized algorithm for subset feedback vertex set in tournaments ⋮ Recognizing when a preference system is close to admitting a master list ⋮ Recognizing when a preference system is close to admitting a master list ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ Fixed parameterized algorithms for generalized feedback vertex set problems ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ Unnamed Item ⋮ Domination and Cut Problems on Chordal Graphs with Bounded Leafage ⋮ Efficient algorithms for measuring the funnel-likeness of DAGs ⋮ Subset feedback vertex set in chordal and split graphs ⋮ Parameterized algorithms for generalizations of directed feedback vertex set ⋮ FPT algorithms for generalized feedback vertex set problems

This page was built for publication: Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable