<ol>
<li><p>Daniel Apon linked to the conference version of my paper. I suggest the draft journal version instead: <a href="http://www.cs.brown.edu/people/ws/papers/fast_journal.pdf">http://www.cs.brown.edu/people/ws/papers/fast_journal.pdf</a> .</p></li>
<li><p>On tournament graphs some experimental work suggests that local search does quite well. See Anke van Zuylen and Frans Schalekampf's recent ALENEX paper: <a href="http://www.siam.org/proceedings/alenex/2009/alx09_004_schalekampf.pdf">http://www.siam.org/proceedings/alenex/2009/alx09_004_schalekampf.pdf</a> .</p></li>
<li><p>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.</p></li>
<li><p>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?</p></li>
</ol>

CC BY-SA 3.0
2014-07-06T16:58:05.687Z
Your link to Zuylen and Schalekampf is 404 now;  http://www.informatik.uni-trier.de/~ley/pers/hd/s/Schalekamp:Frans
nodakai
CC BY-SA 2.5
2010-09-27T17:00:18.780Z
2010-09-27T17:00:18.780Z
Warren Schudy
<p>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.</p>

CC BY-SA 2.5
2010-08-24T21:44:52.070Z
Both papers are very interesting. Besides these, is there any submodular function based approach around?
miao
CC BY-SA 2.5
2010-08-29T15:50:31.353Z
Please give links.
Emil
CC BY-SA 2.5
2010-09-11T20:56:50.290Z
@Emil, copy/pasting the name of the paper into Google gives you a PDF on the first hit: [PDF](http://www.cs.brown.edu/~ws/papers/fast_conf.pdf).
Daniel Apon
CC BY-SA 2.5
2010-09-11T21:47:38.293Z
I was merely suggesting a way of improving the answer.
Emil
CC BY-SA 2.5
2010-08-24T14:53:37.180Z
2010-08-24T14:53:37.180Z
D. S.
<p>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.  </p>

<p>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. </p>

<p>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.</p>

CC BY-SA 3.0
2015-10-09T15:11:20.987Z
@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.
G. Bach
CC BY-SA 3.0
2015-06-07T09:23:30.473Z
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?
TomR
CC BY-SA 3.0
2017-03-01T13:31:30.427Z
maybe that helps : https://arxiv.org/pdf/1702.07612.pdf cheers
and good luck
user44477
CC BY-SA 2.5
2010-08-23T19:31:36.563Z
I guess you are aware of Even, Naor, Schieber, Sudan (1998): "Approximating Minimum Feedback Sets and Multicuts in Directed Graphs" – http://dx.doi.org/10.1007/PL00009191 ?
Jukka Suomela
CC BY-SA 2.5
2010-09-29T21:38:08.353Z
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 http://www.cs.brown.edu/~ws/papers/fast_journal.pdf .
Warren Schudy
<ds.data-structures><graph-theory><np-hardness><approximation-algorithms>
Any fast algorithm for minimum cost feedback arc set problem?
miao
# Any fast algorithm for minimum cost feedback arc set problem?

(Asked by: username_0 on 2010-08-23)

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.

**Tags:** ds.data-structures, graph-theory, np-hardness, approximation-algorithms

> **Comments:**
> **username_4**: I guess you are aware of Even, Naor, Schieber, Sudan (1998): "Approximating Minimum Feedback Sets and Multicuts in Directed Graphs" – http://dx.doi.org/10.1007/PL00009191 ?  
> **username_5**: 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 http://www.cs.brown.edu/~ws/papers/fast_journal.pdf .  
> **username_2**: 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?  
> **username_1**: @username_2 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.  
> **username_3**: maybe that helps : https://arxiv.org/pdf/1702.07612.pdf cheers and good luck  

---

## 2 answers

### Answer by username_5 on 2010-09-27. Score: 7

1. username_9 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?

> **Comments:**
> **username_6**: Your link to Zuylen and Schalekampf is 404 now;  http://www.informatik.uni-trier.de/~ley/pers/hd/s/Schalekamp:Frans  

---

### Answer by username_7 on 2010-08-24. Score: 5

See the paper "How to Rank with Few Errors: A PTAS for Weighted Feedback Arc Set on Tournaments" by Claire Kenyon-Mathieu and username_5 (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.

> **Comments:**
> **username_0**: Both papers are very interesting. Besides these, is there any submodular function based approach around?  
> **username_8**: Please give links.  
> **username_9**: @username_8, copy/pasting the name of the paper into Google gives you a PDF on the first hit: [PDF](http://www.cs.brown.edu/~ws/papers/fast_conf.pdf).  
> **username_8**: I was merely suggesting a way of improving the answer.  

---

