Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth

We present a parallel algorithm for the (1ε)-approximate maximum flow problem in capacitated, undirected graphs with n vertices and m edges, achieving O(ε -3 polylog n) depth and O(mε -3 polylog n) work in the PRAM model. Although near-linear time sequential algorithms for this problem have been known for almost a decade, no parallel algorithms that simultaneously achieved polylogarithmic depth and near-linear work were known.

At the heart of our result is a polylogarithmic depth, near-linear work recursive algorithm for computing congestion approximators. Our algorithm involves a recursive step to obtain a low-quality congestion approximator followed by a "boosting" step to improve its quality which prevents a multiplicative blow-up in error. Similar to Peng [SODA'16], our boosting step builds upon the hierarchical decomposition scheme of Räcke, Shah, and Täubig [SODA'14]. A direct implementation of this approach, however, leads only to an algorithm with n o(1) depth and m 1+o(1) work. To get around this, we introduce a new hierarchical decomposition scheme, in which we only need to solve maximum flows on subgraphs obtained by contracting vertices, as opposed to vertex-induced subgraphs used in Räcke, Shah, and Täubig [SODA'14]. This in particular enables us to directly extract congestion approximators for the subgraphs from a congestion approximator for the entire graph, thereby avoiding additional recursion on those subgraphs. Along the way, we also develop a parallel flowdecomposition algorithm that is crucial to achieving polylogarithmic depth and may be of independent interest.

We extend our results to related graph problems such as sparsest and balanced sparsest cuts, fair and isolating cuts, approximate Gomory-Hu trees, and hierarchical clustering. All algorithms achieve polylogarithmic depth and near-linear work.

Finally, our PRAM results also imply the first polylogarithmic round, near-linear total space MPC algorithms for approximate undirected maximum flows, as well as all its aforementioned applications in the fully scalable regime where the local machine memory is O(n δ ) for any constant δ > 0.