Expander decompositions have become one of the central frameworks in the design of fast algorithms. For an undirected graph $G=(V,E)$, a near-optimal $\phi$-expander decomposition is a partition $V_1, V_2, \ldots, V_k$ of the vertex set $V$ where each subgraph $G[V_i]$ is a $\phi$-expander, and only an $\widetilde{ O}(\phi)$-fraction of the edges cross between partition sets. In this article, we give the first near-optimal parallel algorithm to compute $\phi$-expander decompositions in near-linear work $\widetilde{ O}(m/\phi^2)$ and near-constant span $\widetilde{ O}(1/\phi^4)$. Our algorithm is very simple and likely practical. Our algorithm can also be implemented in the distributed Congest model in $\tilde{ O}(1/\phi^4)$ rounds. Our results surpass the theoretical guarantees of the current state-of-the-art parallel algorithms [Chang-Saranurak PODC'19, Chang-Saranurak FOCS'20], while being the first to ensure that only an $\tilde{ O}(\phi)$ fraction of edges cross between partition sets. In contrast, previous algorithms [Chang-Saranurak PODC'19, Chang-Saranurak FOCS'20] admit at least an $O(\phi^{ 1/3})$ fraction of crossing edges, a polynomial loss in quality inherent to their random-walk-based techniques. Our algorithm, instead, leverages flow-based techniques and extends the popular sequential algorithm presented in [Saranurak-Wang SODA'19].
Categories: cs.DS