An o(n(3))-time maximum-flow algorithm

We show that a maximum flow in a network with n vertices can be computed deterministically in O(n(3)/logn) time on a uniform-cost RAM. For dense graphs, this improves the previous best bound of O(n(3)). The bottleneck in our algorithm is a combinatorial problem on (unweighted) graphs. The number of operations executed on Bow variables is O(n(8/3)(log n)(4/3)), in contrast with Omega(nm) flow operations for all previous algorithms, where m denotes the number of edges in the network. A randomized version of our algorithm executes O(n(3/2)m(1/2)logn+n(2)(logn)(2)/log(2+n(logn)(2)/m)) flow operations with high probability. For the special case in which all capacities are integers bounded by U, we show that a maximum flow can be computed deterministically using O(n(3/2)m(1/2)+n(2)(logU)(1/2)+logU) Bow operations and O(min{nm,n(3)/logn}+n(2)(logU)(1/2)+logU) time. We finally argue that several of our results yield parallel algorithms with optimal speedup.