Eliminating cyclic flows from a graph

Question

I have a directed graph with flow volumes along edges and I would like to simplify it by removing all cyclic flows. This can be done by finding the minimum of the flow volumes along each edge in any given cycle and reducing the flows of every edge in the cycle by that minimum volume, deleting edges with zero flow. When all cyclic flows have been removed the graph will be acyclic.

For example, if I have a graph with vertices A, B and C with flows of 1 from A→B, 2 from B→C and 3 from C→A then I can rewrite this with no flow from A→B, 1 from B→C and 2 from C→A. The number of edges in the graph has reduced from 3 to 2 and the resulting graph is acyclic.

Which algorithm(s), if any, solve this problem?

Answer 1

You may find it useful to use the flow decomposition theorem (see §6.2 of this discussion of max-flow), which says that any flow can be broken down into a set of flow paths and flow cycles. Moreover, there can be at most m total flow paths and cycles in the graph. This means that one simple algorithm for eliminating flow cycles would be to find all of the flow paths in the graph, then remove all remaining flow in the graph since it must correspond to flow cycles.

To find a flow path or cycle, you can use a simple depth-first search from the source node. Starting at the source node, keep following edges however you'd like until either you hit the terminal node or you visit a node you've previously visited. If you hit the terminal node, then the path you've taken is a simple flow path. If you encounter some node twice, you've just found a flow cycle (formed by the loop that you just found). If you then remove the flow path/cycle from the graph and repeat, you will end up detecting all flow paths and cycles. You know that you're done when there are no flow-carrying edges leaving the source code. If each time that you find a flow path you record the total flow across all of its edges, you can eliminate cyclic flow by repeating this until no flow paths remain, clearing the flow in the network, then adding back in the flow paths.

Since each DFS takes time O(m + n) and there are at most O(m) flow paths, the total runtime of this step is O(m² + mn), which is a polynomial in the size of the graph.

Hope this helps!