A fixed-parameter algorithm for the directed feedback vertex set problem

DOI10.1145/1411509.1411511zbMath1325.68104OpenAlexW2016590962WikidataQ59650040 ScholiaQ59650040MaRDI QIDQ3452187

Igor Razgon, Yang Liu, Barry O'Sullivan, Songjian Lu, Jian'er Chen

Publication date: 11 November 2015

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1411509.1411511

zbMATH Keywords

feedback vertex setparameterized computationdeadlock

Mathematics Subject Classification ID

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

Related Items (63)

Linear kernels for separating a graph into components of bounded size ⋮ On the Complexity of Singly Connected Vertex Deletion ⋮ On Polynomial Kernels for Structural Parameterizations of Odd Cycle Transversal ⋮ Backdoors to Satisfaction ⋮ FPT Suspects and Tough Customers: Open Problems of Downey and Fellows ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Approximations of arbitrary relations by partial orders ⋮ On the feedback number of 3-uniform linear extremal hypergraphs ⋮ A polynomial kernel for funnel arc deletion set ⋮ Component order connectivity in directed graphs ⋮ Towards a polynomial kernel for directed feedback vertex set ⋮ Dynamics and control at feedback vertex sets. I: Informative and determining nodes in regulatory networks ⋮ The complexity of speedrunning video games ⋮ Clique Cover and Graph Separation ⋮ Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ Inapproximability of $H$-Transversal/Packing ⋮ Tight Localizations of Feedback Sets ⋮ An Exact Method for the Minimum Feedback Arc Set Problem ⋮ A parameterized algorithm for subset feedback vertex set in tournaments ⋮ Recognizing when a preference system is close to admitting a master list ⋮ Finding kernels or solving SAT ⋮ Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables ⋮ Unnamed Item ⋮ A faster FPT algorithm for bipartite contraction ⋮ An \(O^\ast(1.84^k)\) parameterized algorithm for the multiterminal cut problem ⋮ Confronting intractability via parameters ⋮ Chordless Cycle Packing Is Fixed-Parameter Tractable ⋮ A spin glass approach to the directed feedback vertex set problem ⋮ Two Hardness Results on Feedback Vertex Sets ⋮ Multi-Budgeted Directed Cuts ⋮ Clustering with Local Restrictions ⋮ A Polynomial Kernel for Funnel Arc Deletion Set. ⋮ Polynomial kernels for deletion to classes of acyclic digraphs ⋮ On parameterized independent feedback vertex set ⋮ Augmenting tractable fragments of abstract argumentation ⋮ Fixed-parameter tractability results for feedback set problems in tournaments ⋮ Component order connectivity in directed graphs ⋮ Kernels for packing and covering problems ⋮ Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems ⋮ Efficient algorithms for measuring the funnel-likeness of DAGs ⋮ Exact localisations of feedback sets ⋮ A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems ⋮ On the Hardness and Inapproximability of Recognizing Wheeler Graphs ⋮ Parameterized algorithms for generalizations of directed feedback vertex set ⋮ FPT is characterized by useful obstruction sets ⋮ An FPT algorithm for edge subset feedback edge set ⋮ Triangle edge deletion on planar glasses-free RGB-digraphs ⋮ Important Separators and Parameterized Algorithms ⋮ Parameterized Complexity of Eulerian Deletion Problems ⋮ Parameterised algorithms for deletion to classes of DAGs ⋮ On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem ⋮ Multi-budgeted directed cuts ⋮ Acyclic Digraphs ⋮ On the complexity of singly connected vertex deletion ⋮ Backdoors to tractable answer set programming ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the space and circuit complexity of parameterized problems: classes and completeness ⋮ An Improved Exact Algorithm for Undirected Feedback Vertex Set ⋮ An improved exact algorithm for undirected feedback vertex set ⋮ On the complexity of recognizing Wheeler graphs ⋮ On group feedback vertex set parameterized by the size of the cutset

This page was built for publication: A fixed-parameter algorithm for the directed feedback vertex set problem