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 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
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/14410
