Near-Optimal Distributed Maximum Flow

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)· nᵒ⁽¹⁾ 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 bound of O(n²), and it nearly matches the Ω̃(D+√n)-round complexity lower bound. The development of the algorithm entails two subresults of independent interest: (i) A (D+√n)· nᵒ⁽¹⁾-round distributed construction of a spanning tree of average stretch nᵒ⁽¹⁾. (ii) A (D+√n)· nᵒ⁽¹⁾-round distributed construction of an nᵒ⁽¹⁾-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)· nᵒ⁽¹⁾ rounds. All our algorithms make use of randomization and succeed with high probability.