Fast Cycle Canceling Algorithms forMinimum Cost Submodular Flow*

This paper presents two fast cycle canceling algorithmsfor the submodular ow problem. The rst uses an assignmentproblem whose optimal solution identies most negativenode-disjoint cycles in an auxiliary network. Canceling thesecycles lexicographically makes it possible to obtain an optimalsubmodular ow in O(n ⁴ h log(nC)) time, which almost matches thecurrent fastest weakly polynomial time for submodular flow(where n is the number ofnodes, h is the time forcomputing an exchange capacity, and C is the maximum absolute value of arccosts). The second algorithm generalizes Goldbergs cyclecanceling algorithm for min cost flow to submodular flow to alsoget a running time of O(n ⁴ h log(nC)).. We show how to modify thesealgorithms to make them strongly polynomial, with running timesof O(n ⁶ h log n), which matches the fastest stronglypolynomial time bound for submodular flow. We also show how toextend both algorithms to solve submodular flow with separableconvex objectives. * An extended abstract of a preliminary version ofpart of this paper appeared in [22]. Research supported in part by a Grant-in-Aid ofthe Ministry of Education, Science, Sports and Culture ofJapan. Research supported by an NSERC Operating Grant.Part of this research was done during a sabbatical leave atCornell SORIE.§ Research supported in part by a Grant-in-Aid ofthe Ministry of Education, Science, Sports and Culture ofJapan.