A fast and effective heuristic for the feedback arc set problem

Let G=(V, A) denote a simple connected directed graph, and let n=|V|, m=|A|, where nt-1≤m≤(n2) A feedback arc set (FAS) of G, denoted R(G), is a (possibly empty)set of arcs whose reversal makes G acyclic. A minimum feedback arc set of G, denoted R∗(G), is a FAS of minimum cardinality r∗(G); the computation of R∗(G) is called the FAS problem. Berger and Shor have recently published an algorithm which, for a given digraph G, computes a FAS whose …