[Solved]: Approximation algorithm for Feedback Arc Set

Problem Detail: 

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.

Asked By : amir079

Answered By : Luke Mathieson

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 tractable¹, 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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/14410