Approximation algorithm for Feedback Arc Set

Given a directed graph $G = (V,A)$, a feedback arc set is a set of arcs whose removal leaves an acyclic graph. The problem is to find the minimum cardinality such set.

I want to find out about is there some approximation algorithm around this problem.

• What do you want to know about this problem? The corresponding decision problem is NP-complete. Sep 18, 2013 at 9:30
• Then please edit your post and add details as to what you are looking for, and what you have already tried. You are likely to get more answers that way. Sep 18, 2013 at 9:37
• If you are looking for an approximation algorithm, did you try googling for it? You'll find plenty of material.
– Juho
Sep 18, 2013 at 19:55
• @Shaull is there a fancy name for the problem? Sep 19, 2013 at 2:54
• "Feedback set" is the correct name. Fancy enough, I think. Sep 19, 2013 at 5:30

Kann's online compendium of NPO problems is a good place to start. Feedback Arc Set (the "Directed part is redundant when you use "arc") is:

• APX-hard,
• Approximable within $\mathcal{O}(\log n \log \log n)$ (where $n$ is the number of vertices).

The problem is also fixed-parameter tractable1, so it might make more sense to solve the problem exactly, rather than use what looks like a bad approximation algorithm. (Or as Pål points out below, the running time is a bit... unpleasant, so maybe not.)

Notes

1 - JACM publication, Razgon & Sullivan's preprint, Chen, Liu and Lu's preprint - the problem was independently solved and the results combined to one publication

• Just because there's an FPT algorithm, doesn't really mean it makes more sense to solve the problem exactly. Especially not when the running time is $\Omega(n^4 k!)$. (Disclaimer: I have no idea what the best running time known for FAS is!) Sep 19, 2013 at 8:47
• BTW, is there anything like Kann's list that would be more up to date? Seems like the last update is from 2000. Probably not though...
– Juho
Sep 19, 2013 at 13:38
• I don't know of any similar resource unfortunately. It's a good starting point, but if you were serious, it's back to the more laborious search methods. Sep 20, 2013 at 0:00