We provide new, improved bounds for approximating the sparsest cut value or the conductance (\phi) of a graph in the CONGEST model. Our main result presents an algorithm running in (O(\log^2 n / \phi)) rounds where each vertex outputs a value (\tilde \phi) satisfying (\phi \leq \tilde \phi \leq \sqrt{2.01\phi}). In most regimes, our algorithm significantly improves over the previously fastest algorithm [Chen, Meierhans, Probst Gutenberg, Saranurak; SODA 25]. Additionally, our result generalizes to (k)-way conductance.
We obtain these results by approximating the eigenvalues of the normalized Laplacian matrix [L = I - \text{Deg}^{-1/2}A\text{Deg}^{-1/2}], where (A) is the adjacency matrix and Deg is the diagonal matrix with weighted degrees. We show our algorithms are near-optimal by proving a lower bound for computing the smallest non-trivial eigenvalue of (L), even in the stronger LOCAL model.
The previous state-of-the-art sparsest cut algorithm is in the technical realm of expander decompositions, while our algorithms are relatively simple and easy to implement. At the core, they rely on the well-known power method, which involves repeatedly multiplying the Laplacian with a vector. This operation can be performed in a single round in the CONGEST model. All our algorithms apply to weighted, undirected graphs, and our lower bounds apply even in unweighted graphs.
Blogger's Review: The algorithm proposed in this paper significantly enhances the computational efficiency of the sparsest cut problem through a straightforward yet effective eigenvalue estimation method. It offers a new perspective for the development of graph algorithms, especially with great potential for application in distributed environments. Compared to traditional complex algorithms, it demonstrates better practicality and implementability.