Can a maximum flow be computed in o(nm) time?

Abstract

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)^3/2+n ²(log n)²) flow operations with high probability.

Specializing to the case in which all capacities are integers bounded by U, we show that a maximum flow can be computed using O(n ^3/2 m ^1/2+n ²(log U)^1/2) flow operations. Finally, we argue that several of our results yield optimal parallel algorithms.

This research was partially supported by the ESPRIT II Basic Research Actions Program of the EC under contract No. 3075 (project ALCOM).