# 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. – Shaull Sep 18 '13 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. – Shaull Sep 18 '13 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 '13 at 19:55
• @Shaull is there a fancy name for the problem? – Subhayan Sep 19 '13 at 2:54
• "Feedback set" is the correct name. Fancy enough, I think. – Shaull Sep 19 '13 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!) – Pål GD Sep 19 '13 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 '13 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. – Luke Mathieson Sep 20 '13 at 0:00