# Feedback vertex set

A **feedback vertex set** in a graph is a set of vertices whose removal leaves the graph acyclic; the Feedback Vertex Set (FVS) problem asks for such a set of minimum size, or, in its decision form, whether a graph G contains one of size at most a given integer k. The problem is one of the most studied vertex deletion problems in graph algorithms, was among the first problems shown to be NP-complete, and has been studied intensively from the viewpoints of approximation algorithms and parameterized complexity.<sup>[1](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.56)</sup>

| Key fact | Detail |
|---|---|
| Definition | A vertex set S such that G − S is acyclic; the decision version asks whether one of size at most k exists<sup>[1](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.56)</sup> |
| Complexity | NP-complete; among the first problems shown NP-complete<sup>[1](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.56)</sup> |
| Best polynomial approximation | Factor 2 for the undirected problem<sup>[1](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.56)</sup> |
| Inapproximability | Under the Unique Games Conjecture, no polynomial-time approximation factor better than 2 is possible<sup>[2](https://www.sciencedirect.com/science/article/pii/S0304397526003105)</sup> |
| Fastest FPT algorithms | Deterministic \( \mathcal{O}^{*}(3.460^{k}) \); randomized \( \mathcal{O}^{*}(2.7^{k}) \)<sup>[1](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.56)</sup> |
| Kernelization | A kernel of size \( \mathcal{O}(k^{2}) \) computable in \( \mathcal{O}(k^{4} m) \) time on a graph with m edges<sup>[3](https://arxiv.org/abs/1608.01463)</sup> |
| Directed version | Fixed-parameter tractable, resolved in 2008 with a \( 2^{\mathcal{O}(k \log k)} \cdot n^{\mathcal{O}(1)} \) algorithm<sup>[4](https://arxiv.org/abs/1707.01470)</sup> |

## Variants and basic structure

The problem comes in vertex and edge versions, each for directed and undirected graphs. A feedback vertex (edge) set is a subset S of vertices (F of edges) such that the remaining graph is acyclic; the directed edge version is usually called feedback arc set.<sup>[5](https://doi.org/10.1016/j.tcs.2021.10.017)</sup> The two edge cases differ sharply in difficulty: computing a minimum feedback edge set in an undirected graph is equivalent to finding a maximum-size spanning tree and is solvable in polynomial time, while finding a minimum feedback vertex set, or a minimum [feedback arc set](https://www.edgepedia.org/feedback-arc-set), is NP-hard. Even in restricted classes the vertex problem remains hard in general, though minimum feedback vertex sets can be determined in polynomial time in (sub-)cubic graphs.<sup>[5](https://doi.org/10.1016/j.tcs.2021.10.017)</sup>

A useful structural fact underlies several algorithms: in a graph with minimum degree at least 3, at least half of all edges are incident on any feedback vertex set.<sup>[2](https://www.sciencedirect.com/science/article/pii/S0304397526003105)</sup>

## Approximation

The best-known polynomial-time approximation algorithm for undirected FVS achieves a factor of 2.<sup>[1](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.56)</sup> This factor is also the best one can hope for in polynomial time under the Unique Games Conjecture, a standard assumption in inapproximability theory.<sup>[2](https://www.sciencedirect.com/science/article/pii/S0304397526003105)</sup> Fujito showed that vertex cover and feedback vertex set in undirected graphs are structurally closely related through the standard vector spaces of a graph, and that both can be approximated within the same factor of 2 by essentially the same heuristics.<sup>[6](https://www.sciencedirect.com/science/article/pii/0020019096000944)</sup>

For the directed version, the approximability picture is less settled: an \( \widetilde{O}(\log n) \)-factor approximation can be found efficiently, while efficient constant-factor approximation is ruled out under the Unique Games Conjecture.<sup>[7](https://www.theoryofcomputing.org/articles/v012a006/)</sup>

**Parameterized approximation.** A 2023 line of work combines the two paradigms. For every \( \epsilon \in (0,1) \) there is a randomized algorithm that, given an instance (G, k), either reports failure or finds a feedback vertex set of size at most \( (1+\epsilon)k \), succeeding with probability at least 1/e when a solution of size k exists. Three algorithms with running times \( \mathcal{O}^{*}(2^{\epsilon k} \cdot 2.7^{(1-\epsilon)k}) \), \( \mathcal{O}^{*}(((4/(1+\epsilon))^{(1+\epsilon)} \cdot (\epsilon/3)^{\epsilon})^{k}) \), and \( \mathcal{O}^{*}(4^{(1-\epsilon)k}) \) each dominate over some range of ε, and combining them gives a factor \( (1+\epsilon) \) approximation that runs faster than the best known randomized FPT algorithm for every ε in (0, 1).<sup>[1](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.56)</sup><sup> • </sup><sup>[2](https://www.sciencedirect.com/science/article/pii/S0304397526003105)</sup> Such schemes are harder to build for FVS than for vertex cover, because the forbidden subgraph, a cycle, can be very large, so neither picking disjoint copies of forbidden structures nor bounded branching applies directly.<sup>[2](https://www.sciencedirect.com/science/article/pii/S0304397526003105)</sup>

## Parameterized algorithms

FVS is a landmark problem of parameterized complexity, the study of algorithms with running time \( f(k) \cdot n^{c} \) for a parameter k. A long line of research produced multiple algorithmic approaches and a sustained race for the fastest exponential dependence on k, and the first Parameterized Algorithms and Computational Experiments Challenge (PACE) in 2016 featured FVS as one of its tracks; that competition indicated an approach based on half-integral relaxations as probably the most efficient in practice.<sup>[8](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.12)</sup> The current fastest exact algorithms run in \( \mathcal{O}^{*}(3.460^{k}) \) deterministically and \( \mathcal{O}^{*}(2.7^{k}) \) randomized.<sup>[1](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.56)</sup>

Preprocessing is also well understood: an algorithm running in \( \mathcal{O}(k^{4} m) \) time reduces an instance to an equivalent one whose graph has size \( \mathcal{O}(k^{2}) \), a so-called kernel.<sup>[3](https://arxiv.org/abs/1608.01463)</sup> Beyond the standard parameterization by solution size, a systematic classification of structural parameters shows, for example, that FVS is fixed-parameter tractable parameterized by the vertex-deletion distance to a chordal graph, and admits a polynomial kernel parameterized by the vertex-deletion distance to a pseudoforest, a graph in which every connected component has at most one cycle.<sup>[9](https://www.sciopen.com/article/10.1109/TST.2014.6867520)</sup>

## The directed version

Directed Feedback Vertex Set (DFVS), which asks for a smallest vertex set hitting all cycles of a digraph, is one of [Karp's 21 NP-complete problems](https://www.edgepedia.org/karps-21-np-complete-problems), and establishing its fixed-parameter tractability was a major open problem for decades. Chen, Liu, Lu, O'Sullivan, and Razgon resolved it in 2008 with a \( 2^{\mathcal{O}(k \log k)} \cdot n^{\mathcal{O}(1)} \) algorithm combining iterative compression with important separators; a later refinement reduced the dependence on graph size to linear while keeping the same dependence on k. Whether the running time can be improved to \( 2^{\mathcal{O}(k)} \cdot n^{\mathcal{O}(1)} \) remains open, as does the existence of a polynomial kernel for DFVS on general digraphs.<sup>[4](https://arxiv.org/abs/1707.01470)</sup>

Parameterizing by treewidth t of the underlying undirected graph, dynamic programming solves DFVS in \( 2^{\mathcal{O}(t \log t)} \cdot n^{\mathcal{O}(1)} \) time, which is optimal under the Exponential Time Hypothesis; on planar digraphs the bound improves to \( 2^{\mathcal{O}(t)} \cdot n^{\mathcal{O}(1)} \), yielding a \( 2^{\mathcal{O}(\sqrt{n})} \) algorithm for planar digraphs since planar graphs have treewidth \( \mathcal{O}(\sqrt{n}) \).<sup>[4](https://arxiv.org/abs/1707.01470)</sup>

## Applications

The problem arises wherever cycles in a modeled system must be broken. In operating systems and database systems, the wait-for graph records which processes wait for which resources, and each directed cycle corresponds to a deadlock; a minimum feedback vertex set in this graph corresponds to the minimum number of processes that must be aborted to resolve all deadlocks.<sup>[10](https://www.mdpi.com/1999-4893/6/4/726)</sup> In Bayesian networks, finding a small loop cutset is the first step of the method of conditioning for inference, and an algorithm based on a reduction to the weighted feedback vertex set problem with a 2-approximation guarantees a cutset with fewer than twice the variables of a minimum one.<sup>[11](https://www.sciencedirect.com/science/article/pii/0004370295000046)</sup> Weighted and minimum feedback vertex sets have also been applied to detecting human cancer genes, using integer linear programming formulations over a compressed graph.<sup>[12](https://pmc.ncbi.nlm.nih.gov/articles/PMC7986389/)</sup>

## References

1. [Parameterized Approximation Scheme for Feedback Vertex Set, MFCS 2023 (LIPIcs)](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.56)
2. [Parameterized approximation scheme for feedback vertex set, Theoretical Computer Science](https://www.sciencedirect.com/science/article/pii/S0304397526003105)
3. [Linear-time Kernelization for Feedback Vertex Set, arXiv](https://arxiv.org/abs/1608.01463)
4. [On Directed Feedback Vertex Set parameterized by treewidth, arXiv](https://arxiv.org/abs/1707.01470)
5. [On the complexity of solution extension of optimization problems, Theoretical Computer Science](https://doi.org/10.1016/j.tcs.2021.10.017)
6. [A note on approximation of the vertex cover and feedback vertex set problems, Information Processing Letters](https://www.sciencedirect.com/science/article/pii/0020019096000944)
7. [Simple Proof of Hardness of Feedback Vertex Set, Theory of Computing](https://www.theoryofcomputing.org/articles/v012a006/)
8. [Experimental Evaluation of Parameterized Algorithms for Feedback Vertex Set, SEA 2018 (LIPIcs)](https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.12)
9. [Parameter Ecology for Feedback Vertex Set, Tsinghua Science and Technology](https://www.sciopen.com/article/10.1109/TST.2014.6867520)
10. [An Efficient Local Search for the Feedback Vertex Set Problem, Algorithms (MDPI)](https://www.mdpi.com/1999-4893/6/4/726)
11. [Optimization of Pearl's method of conditioning and greedy-like approximation algorithms for the vertex feedback set problem, Artificial Intelligence](https://www.sciencedirect.com/science/article/pii/0004370295000046)
12. [Weighted minimum feedback vertex sets and implementation in human cancer genes detection, PMC](https://pmc.ncbi.nlm.nih.gov/articles/PMC7986389/)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › General discrete mathematics and discrete structures › Graph theory › Graph invariants and parameters › Acyclic and orientation invariants*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license