In a directed graph, $G=(V,E)$, $F\subset E$, if $G\setminus F$ is a DAG(directed acyclic graph), $F$ is called a feedback arc set.

If each edge is associated with a weight $w$, the minimum cost feedback arc set problem is to find a $F$ such that $W(F)$ is minimum.

It is well-known that minimum feedback arc set problem is NP-hard, and so does minimum cost feedback arc set problem. I wonder if anyone knows any approximate algorithm that performs well, and any properties of the weight function that can yield a fast solver.

  • 2
    $\begingroup$ I guess you are aware of Even, Naor, Schieber, Sudan (1998): "Approximating Minimum Feedback Sets and Multicuts in Directed Graphs" – dx.doi.org/10.1007/PL00009191 ? $\endgroup$ Commented Aug 23, 2010 at 19:31
  • $\begingroup$ There were several independent discoveries of polylogarithmic approximations for general feedback arc set. Depending on what precisely you're looking for you may wish to look at all of them. See the papers Leighton and Rao 1999; Seymour 1995; Even et al. 2000; Even et al. 1998 cited in my cs.brown.edu/~ws/papers/fast_journal.pdf . $\endgroup$ Commented Sep 29, 2010 at 21:38
  • $\begingroup$ Just wanted to make it clear - is this right that only directed problem is NP-hard and the problem for non-directed graphs can be solved in polynomial time, see, e.g. stackoverflow discussion "How to find feedback edge set in undirected graph". Is this right that the problem can be solved in polynomial time for nondirected graph? $\endgroup$
    – TomR
    Commented Jun 7, 2015 at 9:23
  • 1
    $\begingroup$ @TomR A minimum weight feedback edge set in an undirected graph has a maximum weight spanning tree as its complement, which you can find in polytime. $\endgroup$
    – G. Bach
    Commented Oct 9, 2015 at 15:11
  • $\begingroup$ maybe that helps : arxiv.org/pdf/1702.07612.pdf cheers and good luck $\endgroup$
    – user44477
    Commented Mar 1, 2017 at 13:31

2 Answers 2

  1. Daniel Apon linked to the conference version of my paper. I suggest the draft journal version instead: http://www.cs.brown.edu/people/ws/papers/fast_journal.pdf .

  2. On tournament graphs some experimental work suggests that local search does quite well. See Anke van Zuylen and Frans Schalekampf's recent ALENEX paper: http://www.siam.org/proceedings/alenex/2009/alx09_004_schalekampf.pdf .

  3. If the weights satisfy either "probability constraints" or "triangle inequalities" there's a constant-factor approximation algorithm based on quicksort. See Ailon, Charikar and Newman's recent JACM paper.

  4. Can you tell us a bit more about what sorts of instances you have in mind and whether you're looking for something that works well in practice or in theory?


See the paper "How to Rank with Few Errors: A PTAS for Weighted Feedback Arc Set on Tournaments" by Claire Kenyon-Mathieu and Warren Schudy (STOC 2007, journal version on Schudy's page), which gives a Polynomial-time approximation scheme for the special case where the directed graph is a tournament.

  • $\begingroup$ Both papers are very interesting. Besides these, is there any submodular function based approach around? $\endgroup$
    – miao
    Commented Aug 24, 2010 at 21:44
  • 1
    $\begingroup$ Please give links. $\endgroup$
    – Emil
    Commented Aug 29, 2010 at 15:50
  • $\begingroup$ @Emil, copy/pasting the name of the paper into Google gives you a PDF on the first hit: PDF. $\endgroup$ Commented Sep 11, 2010 at 20:56
  • $\begingroup$ I was merely suggesting a way of improving the answer. $\endgroup$
    – Emil
    Commented Sep 11, 2010 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.