Algorithm for detecting the minimum count of edges to break all loops

user_4949386 0
Viewed 165

enter image description here

Is there an algorithm that takes a directed graph as input, and as output gives the minimum number of edges to "break" in order to prevent loops?

As an example, the loops in the above graph are:

  • A, B, C, D
  • A, B, E
  • E, G, H, F

And the minimum number of edges to break all of them:

    1. A - B, breaks 2 loops
    1. E - G, breaks 1 loop

It gets more complicated when the loops are nested inside each other and share edges.

My current approach is to find all the loops, group by most common edge, order desc, and break them in that order whilst the loops are still unbroken from the previous iterations.

I have tried a few methods and they all vary by the count of edges they break - I'm looking for the minimum theoretically possible.

Is there an established algorithm that does this?

directed-graph graph algorithm
1 Answers

This is the NP-hard Minimum Feedback Arc Set problem. Wikipedia doesn't point at an exact algorithm for small- to medium-size graphs, so let me suggest one.

Using an integer programming solver library such as OR-Tools, we formulate an integer program with a 0-1 variable for each arc, where 0 means retain the arc and 1 means delete the arc. The objective is to minimize the sum of these variables.

Now, we need to specify constraints, but in general there can be an exponential number of cycles, which would quickly overwhelm the solver as the graph grows. Instead, do the following:

  1. Solve the integer program (initially, with no constraints).
  2. Use breadth-first search to find a shortest cycle in the retained edges, if there is one.
  3. If there is a cycle, add a constraint that the sum of the corresponding variables must be greater than or equal to one, then go back to Step 1. Otherwise, the current solution is optimal.
user_21446690
Related