3

Let G be a weighted directed graph containing cycles. I'm looking for an algorithm to find and remove those cycles by removing the least-weight edge of a cycle.

I think potentially I could do several DFS, but was wondering if there are more well-developed solutions out there.

Thanks for the help :)

totoromeow
  • 2,199
  • 4
  • 19
  • 19
  • This might be a duplication (since removing the least weighted edge seems simple after you have a cycle) of: http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph However, I won't flag since there might be algorithms that combine the two steps... – sdasdadas Mar 15 '13 at 21:46
  • are you sure your problem is well-defined? consider the case of 4 path segments `p_i, i=1..4` mutually disjoint apart from their endpoints, where `p_1`, `p_2` link vertices `v` with `w` and `p_3`, `p_4` connect `w` with `v`. assume as well that `p_1`, `p_3` each contain one of exactly 2 edges with globally minimal weights. depending on whether you consider `C1={p_1, p_3}, C2={p_2, p_4}` or `C1'={p_1, p_4}, C2'={p_2, p_3}`, you will remove different edges and end up with a different total weight of the cycle-free graph. – collapsar Mar 21 '13 at 14:25
  • check this algorithm: http://en.wikipedia.org/wiki/Johnson's_algorithm, though it works good for small graphs, and may take forever to do large ones – user1406062 Apr 23 '13 at 09:21

1 Answers1

1

The problem you are trying to solve is known as (Minimum) Feedback Arc Set. This is an NP-hard problem, thus you won't find any efficient, deterministic, optimal algorithms. Also, no "good" approximation algorithms are known. If you known your feedback arc set to be small, there is an FPT algorithm, though. See https://en.wikipedia.org/wiki/Feedback_arc_set#Minimum_feedback_arc_set for details.

Heuristics for the feedback arc set are an active field of research, though. This paper seems to be a good starting point: https://onlinelibrary.wiley.com/doi/abs/10.1002/net.3230200102

Lukas Barth
  • 2,734
  • 18
  • 43
  • This problem appears to be for unweighted directed graphs, so the version for weighted graphs must also be NP-hard, but not exactly the same problem. – kaya3 Jan 17 '20 at 00:08
  • 1
    Oh yes - I apparently overread the "weighted" in the question. Thus, the problem is "Weighted Feedback Arc Set". :) Still NP-hard, still no good approximations, but there's probably less heuristics out there, I'm afraid. – Lukas Barth Jan 17 '20 at 11:49