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