Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
<|reference_start|>Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth: We present a parallel algorithm for the $(1-\epsilon)$-approximate maximum flow problem in capacitated, undirected graphs with $n$ vertices and $m$ edges, achieving $O(\epsilon^{-3}\text{polylog} n)$ depth and $O(m \epsilon^{-3} \text{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\"acke, Shah, and T\"aubig [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\"acke, Shah, and T\"aubig [SODA'14]. In particular, we are able 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 flow-decomposition algorithm that is crucial to achieving polylogarithmic depth and may be of independent interest.<|reference_end|>
@article{agarwal2024parallel,
    title={Parallel Approximate Maximum Flows in Near-Linear Work and
  Polylogarithmic Depth},
    author={Arpit Agarwal, Sanjeev Khanna, Huan Li, Prathamesh Patil, Chen Wang,
  Nathan White, Peilin Zhong},
    journal={arXiv preprint arXiv:2402.14950},
    year={2024},
    doi={10.1137/1.9781611977912.140},
    archivePrefix={arXiv},
    eprint={2402.14950},
    primaryClass={cs.DS}
}