# Feedback arc set
A **feedback arc set** of a directed graph is a set of arcs (directed edges) whose removal makes the graph acyclic, that is, turns it into a directed acyclic graph (DAG). Equivalently, it is a set of arcs containing at least one arc of every directed cycle. The **minimum feedback arc set problem** asks for such a set of smallest cardinality, or of smallest total weight in the weighted version, and is one of the classical NP-hard problems in combinatorial optimization.[1](https://www.mat.univie.ac.at/~herman/fwf-P27891-N32/minimum_feedback_arc_set.pdf) • [2](https://link.springer.com/article/10.1007/s10878-024-01209-8)
| Key fact | Detail |
|---|---|
| Definition | A set of arcs containing at least one arc of every directed cycle; removing it leaves a directed acyclic graph[1](https://www.mat.univie.ac.at/~herman/fwf-P27891-N32/minimum_feedback_arc_set.pdf) |
| Complexity history | The minimum feedback arc set problem was item 8 on Richard M. Karp's list of 21 NP-complete problems[1](https://www.mat.univie.ac.at/~herman/fwf-P27891-N32/minimum_feedback_arc_set.pdf) |
| Hardness of approximation | APX-hard; unless P = NP there is no polynomial-time approximation scheme[1](https://www.mat.univie.ac.at/~herman/fwf-P27891-N32/minimum_feedback_arc_set.pdf) |
| Best general approximation | An O(log n log log n) approximation algorithm due to Seymour[3](https://www.math.ucdavis.edu/~saito/data/digraphs/bang-jensen-gutin_digraph-book.pdf) |
| Tournaments | A polynomial-time approximation scheme for weighted FAS on tournaments, by Kenyon-Mathieu and Schudy (2006)[4](https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-144/index.html) |
| Size bound | Any minimum feedback arc set has size at most |A|/2, since both the forward and the backward arcs of any vertex ordering form feedback arc sets[2](https://link.springer.com/article/10.1007/s10878-024-01209-8) |
| Parameterized status | Fixed-parameter tractable; an O(n44k k3 k!) time algorithm is known for the decision version with parameter k[1](https://www.mat.univie.ac.at/~herman/fwf-P27891-N32/minimum_feedback_arc_set.pdf) |
## Equivalent formulations
The problem has two standard views. In the **deletion view**, one seeks a smallest set of arcs whose removal breaks all directed cycles. In the **ordering view**, introduced by D. Younger in 1963, one seeks a linear ordering of the vertices that minimizes the number of backward arcs, arcs that point from a later vertex to an earlier one; the backward arcs of any ordering form a feedback arc set, and a minimum one is realized by an optimal ordering.[5](https://link.springer.com/article/10.1007/s13278-025-01491-2)This ordering view connects the problem to the **maximum acyclic subgraph** problem, which asks for the largest set of arcs inducing no cycle, and, in its weighted form, to the **Linear Ordering Problem**, which arises in the study of interactions between sectors of an economic system. The two problems are algorithmically equivalent, but approximation guarantees do not transfer automatically between them: a simple O(m)-time procedure finds an acyclic subgraph holding at least half the total arc weight, giving a 2-approximation for the maximum acyclic subgraph, yet this does not yield a 2-approximation for the minimum feedback arc set, because an optimal ordering may have almost all arcs pointing forward while the guaranteed ordering has only about half.[3](https://www.math.ucdavis.edu/~saito/data/digraphs/bang-jensen-gutin_digraph-book.pdf)
A related structural fact is that reversing, rather than deleting, the arcs of a minimal feedback edge set also makes the graph acyclic.[1](https://www.mat.univie.ac.at/~herman/fwf-P27891-N32/minimum_feedback_arc_set.pdf) The vertex analog, the **feedback vertex set** problem, asks for a smallest set of vertices hitting every cycle; the two problems are equally hard to approximate in polynomial time, and reductions between them preserve solution cost.[1](https://www.mat.univie.ac.at/~herman/fwf-P27891-N32/minimum_feedback_arc_set.pdf)
## Computational complexity
The minimum feedback arc set problem is NP-hard on general directed graphs and APX-hard, so, unless P = NP, it admits no polynomial-time approximation scheme.[1](https://www.mat.univie.ac.at/~herman/fwf-P27891-N32/minimum_feedback_arc_set.pdf) Approximating the number of arcs in an optimal solution is difficult enough that, as of the survey literature, no c-approximation algorithm for any constant c was known for the general problem; the best known general guarantee is an O(log n log log n) approximation due to Paul Seymour, made explicit by Even, Naor, Schieber, and Sudan.[3](https://www.math.ucdavis.edu/~saito/data/digraphs/bang-jensen-gutin_digraph-book.pdf) • [6](https://snap.stanford.edu/class/cs224w-readings/leighton99mincut.pdf)
Some graph classes are easier. Planar graphs admit a polynomial-time algorithm, due to Lucchesi and Younger (1978).[2](https://link.springer.com/article/10.1007/s10878-024-01209-8) Dense digraphs, including tournaments, admit polynomial-time approximation schemes for the maximum acyclic subgraph problem.[3](https://www.math.ucdavis.edu/~saito/data/digraphs/bang-jensen-gutin_digraph-book.pdf)
From the parameterized perspective, deciding whether a graph has a feedback arc set of size at most k was long open; it is now known to be fixed-parameter tractable, with an O(n44k k3 k!) time algorithm, meaning the running time is polynomial in the graph size whenever k is bounded by a constant.[1](https://www.mat.univie.ac.at/~herman/fwf-P27891-N32/minimum_feedback_arc_set.pdf) The dual problem, asking whether k arcs induce an acyclic subgraph, is fixed-parameter tractable in general directed graphs, while the dual of feedback vertex set is W[1]-hard (class of parameterized problems unlikely to have efficient fixed-parameter algorithms) in general directed graphs.[7](https://www.sciencedirect.com/science/article/pii/S0304397505006365)
## Tournaments and ranking
A tournament is a directed graph in which every pair of vertices is joined by exactly one arc, the natural model of a round-robin competition. Ranking players by the results of such a competition means finding an ordering that minimizes the number of **upsets**, pairs where a lower-ranked player beat a higher-ranked one; this is exactly the minimum feedback arc set problem on tournaments, and it is NP-hard.[4](https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-144/index.html) • [8](https://www.sciencedirect.com/science/article/pii/S0095895619300814)
Tournaments behave much better than general digraphs. Kenyon-Mathieu and Schudy gave a polynomial-time approximation scheme for the weighted problem in 2006, and their weighted generalization yields a PTAS for Kemeny-Young rank aggregation, the problem of combining several individual rankings into one.[4](https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-144/index.html) A PTAS of this kind is impossible for general digraphs, which follows from the in-approximability result of Dinur and Safra.[3](https://www.math.ucdavis.edu/~saito/data/digraphs/bang-jensen-gutin_digraph-book.pdf) On the structural side, a tournament is **cycle Mengerian**, meaning the minimum weight of a feedback arc set equals the maximum size of a cycle packing for every nonnegative integral arc weighting, exactly when it contains none of four Möbius ladders as a subgraph.[8](https://www.sciencedirect.com/science/article/pii/S0095895619300814) Extremal work by Garth Isaak, a mathematician working in combinatorics, bounds how large a tournament can be while having the arcs of an acyclic n-vertex tournament as its minimum feedback arc set: s(n) ≥ 3n − 2 − ⌊log₂ n⌋, and this bound is tight when n = 2k − 2t.[9](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v2i1r20)
## Algorithms in practice
Because exact solution is expensive, practical work relies on heuristics and on exploiting structure. A standard preprocessing step decomposes the graph into strongly connected components, which can be found in Θ(n + m) time, and solves the problem on each cyclic component separately, since the union of per-component feedback arc sets is a feedback arc set for the whole graph.[1](https://www.mat.univie.ac.at/~herman/fwf-P27891-N32/minimum_feedback_arc_set.pdf) • [2](https://link.springer.com/article/10.1007/s10878-024-01209-8)
Several algorithm families are in use:
- **Linear-time heuristics.** The Eades, Lin, and Smyth heuristic (1993) builds an ordering greedily and is implemented in the igraph library as the fast approximation option, alongside an exact integer-programming algorithm that guarantees minimum total weight.[10](https://r.igraph.org/reference/feedback_arc_set.html)
- **Cycle-enumeration exact methods.** For sparse graphs, an exact method that enumerates simple cycles lazily, extending an incomplete cycle matrix iteratively, has in reported cases needed only a tractable number of cycles before finding a minimum feedback arc set.[1](https://www.mat.univie.ac.at/~herman/fwf-P27891-N32/minimum_feedback_arc_set.pdf)
- **Local-search and ordering heuristics.** Recent two-phase methods combine a fast optimization phase with a randomized refinement phase; the Rocket-Crane algorithm delivers solutions retaining roughly 75 to 80 percent of the total edge weight in the feedforward set within 5 seconds on large real-world graphs.[5](https://link.springer.com/article/10.1007/s13278-025-01491-2) Related work searches for feedback arc sets that are both minimal, no arc can be reintroduced without creating a cycle, and stable, with each vertex losing no more outgoing (respectively incoming) arcs than it keeps incoming (respectively outgoing) ones; such algorithms run in O(|V|(|V| + |A|)) time.[2](https://link.springer.com/article/10.1007/s10878-024-01209-8)
## Applications
The problem appears wherever directed cycles must be broken cheaply. Documented application areas include social network analysis, circuit testing, deadlock resolution, and algorithmic games.[11](https://www.sciencedirect.com/science/article/pii/S0305054824001965) Ranking from pairwise comparisons, in sports analytics, preference aggregation, and evaluation, is naturally modeled as finding a minimum-weight feedback arc set in a weighted digraph of comparisons; removing the feedback arcs leaves a DAG whose topological order induces the ranking.[12](https://www.researchgate.net/publication/400455234_Minimum_Weighted_Feedback_Arc_Sets_for_Ranking_from_Pairwise_Comparisons) In [graph drawing](https://www.edgepedia.org/graph-drawing), layered layouts of directed graphs such as the Graphviz dot layout aim edges in a common direction, and feedback arc removal is the standard way to make a cyclic digraph drawable in layers.[13](https://www.graphviz.org/docs/layouts/dot/)
## References
1. [An exact method for the minimum feedback arc set problem (Baharev et al.), SIAM](https://www.mat.univie.ac.at/~herman/fwf-P27891-N32/minimum_feedback_arc_set.pdf)
2. [Efficient heuristics to compute minimal and stable feedback arc sets, Journal of Combinatorial Optimization](https://link.springer.com/article/10.1007/s10878-024-01209-8)
3. [Feedback Sets and Vertex Orderings, Bang-Jensen and Gutin, Digraphs: Theory, Algorithms and Applications](https://www.math.ucdavis.edu/~saito/data/digraphs/bang-jensen-gutin_digraph-book.pdf)
4. [How to rank with few errors: A PTAS for Weighted Feedback Arc Set on Tournaments, Kenyon-Mathieu and Schudy, ECCC TR06-144](https://eccc.weizmann.ac.il/eccc-reports/2006/TR06-144/index.html)
5. [Rocket-crane algorithm for the Feedback Arc Set problem, Social Network Analysis and Mining](https://link.springer.com/article/10.1007/s13278-025-01491-2)
6. [Max-Flow Min-Cut Theorems and Designing Approximation Algorithms, Leighton and Rao](https://snap.stanford.edu/class/cs224w-readings/leighton99mincut.pdf)
7. [Parameterized algorithms for feedback set problems and their duals in tournaments, Theoretical Computer Science 351 (2006)](https://www.sciencedirect.com/science/article/pii/S0304397505006365)
8. [Ranking tournaments with no errors I: Structural description, Journal of Combinatorial Theory B 141 (2020)](https://www.sciencedirect.com/science/article/pii/S0095895619300814)
9. [Tournaments as Feedback Arc Sets, Garth Isaak, Electronic Journal of Combinatorics 2(1) R20 (1995)](https://www.combinatorics.org/ojs/index.php/eljc/article/view/v2i1r20)
10. [feedback_arc_set, igraph R documentation](https://r.igraph.org/reference/feedback_arc_set.html)
11. [Finding small feedback arc sets on large graphs, Computers & Operations Research](https://www.sciencedirect.com/science/article/pii/S0305054824001965)
12. [Minimum Weighted Feedback Arc Sets for Ranking from Pairwise Comparisons](https://www.researchgate.net/publication/400455234_Minimum_Weighted_Feedback_Arc_Sets_for_Ranking_from_Pairwise_Comparisons)
13. [dot, Graphviz documentation](https://www.graphviz.org/docs/layouts/dot/)
---
*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