An o(n³ )-Time Maximum-Flow Algorithm

We show that a maximum flow in a network with n vertices can be computed deterministically in O(n³ / log n) time on a uniform-cost RAM. For dense graphs, this improves the previous best bound of O(n³ ). The bottleneck in our algorithm is a combinatorial problem on (unweighted) graphs. The number of operations executed on flow variables is O(n^8 / 3 (log n)^4 / 3 ), in contrast with Ω (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 log n + n² (log n)² / log (2 + n(log n)² / 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² (log U)^1 / 2 + log U flow operations and O(min \ nm,n³ / log n\ + n² (log U)^1 / 2 + log U) time. We finally argue that several of our results yield parallel algorithms with optimal speedup.