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$ – Jukka Suomela Aug 23 '10 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$ – Warren Schudy Sep 29 '10 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 Jun 7 '15 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 Oct 9 '15 at 15:11
  • $\begingroup$ maybe that helps : arxiv.org/pdf/1702.07612.pdf cheers and good luck $\endgroup$ – user44477 Mar 1 '17 at 13:31
  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 Aug 24 '10 at 21:44
  • 1
    $\begingroup$ Please give links. $\endgroup$ – Emil Aug 29 '10 at 15:50
  • $\begingroup$ @Emil, copy/pasting the name of the paper into Google gives you a PDF on the first hit: PDF. $\endgroup$ – Daniel Apon Sep 11 '10 at 20:56
  • $\begingroup$ I was merely suggesting a way of improving the answer. $\endgroup$ – Emil Sep 11 '10 at 21:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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