patternMinor
Approximation algorithm for Feedback Arc Set
Viewed 0 times
arcapproximationalgorithmforfeedbackset
Problem
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.
I want to find out about is there some approximation algorithm around this problem.
Solution
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:
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
- 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
Context
StackExchange Computer Science Q#14410, answer score: 7
Revisions (0)
No revisions yet.