7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What do you want to know about this problem? The corresponding decision problem is NP-complete. $\endgroup$ – Shaull Sep 18 '13 at 9:30
  • 2
    $\begingroup$ 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. $\endgroup$ – Shaull Sep 18 '13 at 9:37
  • 1
    $\begingroup$ If you are looking for an approximation algorithm, did you try googling for it? You'll find plenty of material. $\endgroup$ – Juho Sep 18 '13 at 19:55
  • $\begingroup$ @Shaull is there a fancy name for the problem? $\endgroup$ – Subhayan Sep 19 '13 at 2:54
  • $\begingroup$ "Feedback set" is the correct name. Fancy enough, I think. $\endgroup$ – Shaull Sep 19 '13 at 5:30
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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!) $\endgroup$ – Pål GD Sep 19 '13 at 8:47
  • $\begingroup$ 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... $\endgroup$ – Juho Sep 19 '13 at 13:38
  • $\begingroup$ 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. $\endgroup$ – Luke Mathieson Sep 20 '13 at 0:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.