FEEDBACK ARC SET

Minimum edges to remove to make a DAG

12
0.30
1x
The Minimum Feedback Arc Set (MFAS) problem asks for the smallest set of directed edges whose removal makes the graph a DAG (directed acyclic graph) with no cycles. MFAS is NP-hard (Karp 1972) but admits a 2-approximation via topological ordering: arrange vertices in a line; for each arc, keep it if it goes left-to-right, remove it otherwise. The removed "backward" arcs form a feedback set. Applications include deadlock prevention in operating systems, ranking in tournament graphs, and Bayesian network structure learning.