A polynomial cycle canceling algorithm for submodular flow

Submodular flow problems, introduced by Edmonds and Giles, generalize network flow problems. Many algorithms for solving network flow problems have been generalized to submodular flow problems, e.g the cycle canceling method of Klein. For network flow problems, the choice of minimum-mean cycles in Goldberg and Tarjan, and the choice of minimum-ratio cycles in Walacher lead to polynomial cycle canceling methods. For submodular flow problems, Cui and Fujishige show finiteness for the minimum-mean cycle method while Zimmermann develops a pseudo-polynomial minimum ratio cycle method. Here, we prove pseudo-polynomiality of a larger class of the minimum-ratio variants and, by combining both methods, we develop a polynomial cycle canceling algorithm for submodular flow problems.