Near-Optimal Distributed Maximum Flow

Summary

We present a near-optimal distributed algorithm for (1+o(1))-approximation of single-commodity maximum flow in undirected weighted networks that runs in (D+ √n)⋅ no(1) communication rounds in the Congest model. Here, n and D denote the number of nodes and the network diameter, respectively. This is the first improvement over the trivial O(m) time bound, and it nearly matches the Ω(D+√n) round complexity lower bound. The algorithm contains two sub-algorithms of independent interest, both with running time (D+√n)⋅ no(1): Distributed construction of a spanning tree of average stretch no(1). Distributed construction of an no(1)-congestion approximator consisting of the cuts induced by O(log n) virtual trees. The distributed representation of the cut approximator allows for evaluation in (D+√n)⋅ no(1) rounds. All our algorithms make use of randomization and succeed with high probability.