A fixed-parameter algorithm for the directed feedback vertex set problem
From MaRDI portal
Publication:3452187
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
Analysis of algorithms and problem complexity (68Q25) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)
Related Items
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
