Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal

Expander decompositions have become one of the central frameworks in the design of fast algorithms. For an undirected graph

] is a φ-expander, and only an O(φ)-fraction of the edges cross between partition sets.

In this article, we give the first near-optimal parallel algorithm to compute φ-expander decompositions in near-linear work O(m/φ 2 ) and near-constant span O(1/φ 4 ). Our algorithm is very simple and likely practical. Our algorithm can also be implemented in the distributed Congest model in Õ(1/φ 4 ) rounds.

Our results surpass the theoretical guarantees of the current state-of-the-art parallel algorithms [CS19, CS20], while being the first to ensure that only an Õ(φ) fraction of edges cross between partition sets. In contrast, previous algorithms [CS19, CS20] admit at least an O(φ 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 [SW19].