Removing cycle dependencies on a directed graph with fixed edges

Question

I have a directed cyclic graph. Some edges are FIXED and may not be removed. The other edges may be removed to break a cycle.

What is the best way to do remove the cycles in this graph? The traversal should be as much as a DFS as possible and start at a given node.

Answer 1

What you can do is use Dijkstra's algorithm: start with a graph containing only the FIXED edges. Then apply an adaptation of the algorithm starting with the graph you already have:

1. Start with the starting node, and all FIXED edges in the component of the starting node. Assume this is a tree.
2. Add the node closest to the tree.
3. Also add any FIXED edges in the component of the node you just added.
4. If all nodes are in the tree, end. Otherwise, go to step 4.

This, of course, assumes that the graph consisting only of the FIXED edges does not contain cycles. If it does, there is no solution (that is, a subgraph without edges, but containing all FIXED edges).

For directed graphs, it's a bit more complicated. In this case, any component of the graph of FIXED edges should be a tree. In the Dijkstra-like algorithm, only roots of these nodes should be candidates to be added to the tree.

Answer 2

Hi,

the problem is understated because you haven't specified e.g. if the graph needs to remain connected, or if you want to remove a "small" number of non-FIXED edges to break all cycles, or if you really need the globally minimum number of non-FIXED edges to be removed.

If the graph does not need to remain connected, just traverse all the edges and remove all non-FIXED ones. That removes all cycles which you can remove without removing FIXED edges.

If you want a simple greedy algorithm to remove edges that is pure DFS, you can use something like this IF the graph remains connected also when you remove some of the non-FIXED edges:

proc recurse(vertex n, vertex_set ns)
  if (n appers_in ns) // it is a cycle
    return BREAK_CYCLE
  else for (e in list_outgoing_edges_from(n))
    np = e.destination
    result = recurse(np, add_to_set(ns, np))
    if (result == BREAK_CYCLE)
      if (e.FIXED)
        return BREAK_CYCLE
      else
        [remove e from the graph]
        return RETRY
      else if (result == RETRY)
        return recurse(n, ns)
    return FINISHED

if (recurse (your_initial_node, empty_vertex_set()))
  [graph contains a cycle through only FIXED edges]
else
  [the reachable component from initial_node has no longer cycles]

Answer 3

I used the following algorithm to solve my problem:

Start with a graph of all fixed edges marked as confirmed

From a start node, recurse through all confirmed edges as well as the not-yet-confirmed ones. But when you're about to recurse down a not-yet-confirmed edge first check if the node that the edge goes to has a path, by following confirmed edges, to a node in the current search tree (i.e. a node with a visiting flag set). This check must be done recursively by following all confirmed edges but this is too slow for me so I will settle here to just check if the node is visiting or if any of the nodes it is confirmed connected to are visiting. This will cover most of my cases but occationally leave cycles in the graph.

After the above step I use Tarjan's algorithm for finding the strongly connected components left in the graph (this can be done in O(V + E) time). The number of strongly connected components will be very small in my cases so I just go through each strongly connected component and remove one removable edge each. Then I do this step again until no more cycles remain in the graph.

This works fine and is fast enough.