A fixed-parameter algorithm for the directed feedback vertex set problem
From MaRDI portal
Recommendations
- Parameterized algorithms for generalizations of directed feedback vertex set
- Parameterized algorithms for generalizations of directed feedback vertex set
- Fixed parameterized algorithms for generalized feedback vertex set problems
- Directed Subset Feedback Vertex Set is fixed-parameter tractable
- Directed subset feedback vertex set is fixed-parameter tractable
- Parameterized and Exact Computation
- An improved exact algorithm for undirected feedback vertex set
- An Improved Exact Algorithm for Undirected Feedback Vertex Set
- Solving the feedback vertex set problem on undirected graphs
- scientific article; zbMATH DE number 1979503
Cited in
(91)- Fixed-parameter algorithms for cochromatic number and disjoint rectangle stabbing via iterative localization
- Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
- Augmenting tractable fragments of abstract argumentation
- Parameterised algorithms for deletion to classes of DAGs
- Fixed-parameter tractability of directed multiway cut parameterized by the size of the cutset
- A parameterized algorithm for subset feedback vertex set in tournaments
- Tight localizations of feedback sets
- A spin glass approach to the directed feedback vertex set problem
- Tree drawings with columns
- The PACE 2022 parameterized algorithms and computational experiments challenge: directed feedback vertex set
- On the parameterized complexity of symmetric directed multicut
- Towards a polynomial kernel for directed feedback vertex set
- Inapproximability of \(H\)-transversal/packing
- An FPT algorithm for edge subset feedback edge set
- Towards a polynomial kernel for directed feedback vertex set
- On polynomial kernels for structural parameterizations of odd cycle transversal
- On parameterized independent feedback vertex set
- Finding kernels or solving SAT
- What's next? Future directions in parameterized complexity
- Multi-budgeted directed cuts
- Clustering with Local Restrictions
- Multi-budgeted directed cuts
- Wannabe bounded treewidth graphs admit a polynomial kernel for directed feedback vertex set
- Approximations of arbitrary relations by partial orders
- Parameterized algorithms for generalizations of directed feedback vertex set
- Digraph coloring and distance to acyclicity
- On directed feedback vertex set parameterized by treewidth
- Directed Subset Feedback Vertex Set is fixed-parameter tractable
- Polynomial kernels for deletion to classes of acyclic digraphs
- On the Complexity of Singly Connected Vertex Deletion
- Exact localisations of feedback sets
- The complexity of speedrunning video games
- Compression via matroids: a randomized polynomial kernel for odd cycle transversal
- Chordless Cycle Packing Is Fixed-Parameter Tractable
- On the complexity of recognizing Wheeler graphs
- Graph-based optimization of epitope coverage for vaccine antigen design
- Search-space reduction via essential vertices
- Backdoors to satisfaction
- A fully polynomial parameterized algorithm for counting the number of reachable vertices in a digraph
- On the space and circuit complexity of parameterized problems: classes and completeness
- On the feedback number of 3-uniform linear extremal hypergraphs
- Acyclic digraphs
- Deterministic Algorithms for the Independent Feedback Vertex Set Problem
- Linear kernels for separating a graph into components of bounded size
- Feedback vertex set in mixed graphs
- Parameterized complexity of Eulerian deletion problems
- Digraph coloring and distance to acyclicity
- On the Hardness and Inapproximability of Recognizing Wheeler Graphs
- On the descriptive complexity of vertex deletion problems
- A subexponential algorithm for ARRIVAL
- Adapting the directed grid theorem into an FPT algorithm
- Confronting intractability via parameters
- Hitting long directed cycles is fixed-parameter tractable
- An improved exact algorithm for undirected feedback vertex set
- A polynomial kernel for funnel arc deletion set
- An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem
- A Complexity Dichotomy for Finding Disjoint Solutions of Vertex Deletion Problems
- Flow-augmentation. I: Directed graphs
- An exact method for the minimum feedback arc set problem
- An Improved Exact Algorithm for Undirected Feedback Vertex Set
- Parameterized complexity of MinCSP over the point algebra
- Subset feedback vertex set in tournaments as fast as without the subset
- Important separators and parameterized algorithms
- When recursion is better than iteration: a linear-time algorithm for directed acyclicity with few error vertices
- A Polynomial Kernel for Funnel Arc Deletion Set.
- On the complexity of singly connected vertex deletion
- Kernels for below-upper-bound parameterizations of the hitting set and directed dominating set problems
- FPT is characterized by useful obstruction sets: connecting algorithms, kernels, and quasi-orders
- Search-space reduction via essential vertices revisited: vertex multicut and cograph deletion
- Backdoors to tractable answer set programming
- Search-space reduction via essential vertices revisited: vertex multicut and cograph deletion
- Triangle edge deletion on planar glasses-free RGB-digraphs
- On the parameterized complexity of deletion to \(\mathcal{H}\)-free strong components
- Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
- Brief announcement: Treewidth modulator: emergency exit for DFVS
- An O^(1.84ᵏ) parameterized algorithm for the multiterminal cut problem
- On knot-free vertex deletion: fine-grained parameterized complexity analysis of a deadlock resolution graph problem
- Single-exponential FPT algorithms for enumerating secluded \(\mathcal{F}\)-free subgraphs and deleting to scattered graph classes
- Component order connectivity in directed graphs
- Dynamics and control at feedback vertex sets. I: Informative and determining nodes in regulatory networks
- Kernels for packing and covering problems
- Component order connectivity in directed graphs
- Clique Cover and Graph Separation
- Flow-augmentation. III: Complexity dichotomy for Boolean CSPS parameterized by the number of unsatisfied constraints
- Search-space reduction via essential vertices
- Two Hardness Results on Feedback Vertex Sets
- Fixed-parameter tractability results for feedback set problems in tournaments
- Recognizing when a preference system is close to admitting a master list
- FPT Suspects and Tough Customers: Open Problems of Downey and Fellows
- A dynamic MaxSAT-based approach to directed feedback vertex sets
- Lossy reduction rules for the directed feedback vertex set problem
This page was built for publication: A fixed-parameter algorithm for the directed feedback vertex set problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3452187)
