Fast cycle canceling algorithms for minimum cost submodular flow (Q1882113)

The authors present two new algorithms for the submodular flow problem on a directed graph, introduced by \textit{J. Edmonds} and \textit{R. Giles} [Ann. Discrete Math. 1, 185--204 (1977; Zbl 0373.05040)]. The key idea for the first algorithm is to use an assignment subproblem for determining a most negative family of node-disjoint cycles in an auxiliary graph. These cycles are repeatedly cancelled by the algorithm. The main idea of the second algorithm is to cancel cycles in the subgraph of negative reduced cost arcs until it is acyclic. At this point a change to dual variables that remove at least one node from participating in next negative cycles is made. It is shown that proposed algorithms can be modified so that the running times of both are \(O(n^6h\log n)\), where \(n\) is the number of nodes and \(h\) is the time for computing an exchange capacity. Finally, the authors consider an extension of the algorithms to submodular flows with separable convex objectives. This paper, despite some unexplained notations, is well worth reading by anyone interested in flow problems on directed graphs.