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 n -1 less than or equal to m less than or equal to ((n)(2)). 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); th e computation of R(G) is called the FAS problem. Berger and Shor have recently published an algorithm which, for a given digraph G, compute s a FAS whose cardinality is at most m/2- c(1)m/Delta(1/2) where Delta is the maximum degree of G and Cl is a constant. Further, they exhibi ted an infinite class G of graphs with the property that for every G e psilon G and some constant C-2, r(G)greater than or equal to m/2-c(2) m/Delta(1/2). Thus the Berger-Shor algorithm provides, in a certain as ymptotic sense, an optimal solution to the FAS problem. Unfortunately, the Berger-Shor algorithm is complicated and requires running time 0( mn). In this paper we present a simple FAS algorithm which guarantees a good (though not optimal) performance bound and executes in time 0(m ). Further, for the sparse graphs which arise frequently in graph draw ing and other applications, our algorithm achieves the same asymptotic performance bound that Berger-Shor does.