11
$\begingroup$

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.

Improve this question
$\endgroup$
5
  • 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, 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$
    – Warren Schudy
    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
    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
    Oct 9, 2015 at 15:11
  • $\begingroup$ maybe that helps : arxiv.org/pdf/1702.07612.pdf cheers and good luck $\endgroup$
    – user44477
    Mar 1, 2017 at 13:31

2 Answers 2

Reset to default
7
$\begingroup$

  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?

Improve this answer
$\endgroup$
1
5
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Both papers are very interesting. Besides these, is there any submodular function based approach around? $\endgroup$
    – miao
    Aug 24, 2010 at 21:44
  • 1
    $\begingroup$ Please give links. $\endgroup$
    – Emil
    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$
    – Daniel Apon
    Sep 11, 2010 at 20:56
  • $\begingroup$ I was merely suggesting a way of improving the answer. $\endgroup$
    – Emil
    Sep 11, 2010 at 21:47

Your Answer

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

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