Logo image
Back
Sublinear-Time Sampling of Spanning Trees in the Congested Clique
Conference proceeding   Open access

Sublinear-Time Sampling of Spanning Trees in the Congested Clique

Sriram V. Pemmaraju, Sourya Roy and Joshua Z. Sobel
Proceedings of the ACM Symposium on Principles of Distributed Computing, pp.337-348
ACM Conferences
PODC '25: ACM Symposium on Principles of Distributed Computing
06/16/2025
DOI: 10.1145/3732772.3733510
Appears in  UI Libraries Support Open Access
url
https://doi.org/10.1145/3732772.3733510View
Published (Version of record) Open Access

Abstract

We present the first sublinear-in-n round algorithm for sampling an approximately uniform spanning tree of an n-vertex graph in the CongestedClique model of distributed computing. In particular, our algorithm requires Õ (n0.657) rounds for sampling a spanning tree within total variation distance 1/nc, for arbitrary constant c > 0, from the uniform distribution. More precisely, our algorithm requires Õ (n1/2+α) rounds, where O (nα) is the running time of matrix multiplication in the CongestedClique model (currently α = 1-2/ω = 0.157, where ω is the sequential matrix multiplication time exponent). We can adapt our algorithm to give exact rather than approximate samples, but with a larger, though still o (n), runtime of Õ(n2/3+α) = O(n0.824). In a remarkable result, Aldous (SIDM 1990) and Broder (FOCS 1989) showed that the first visit edge to each vertex, excluding the start vertex, during a random walk forms a uniformly chosen spanning tree of the underlying graph. The biggest challenge with implementing the Aldous-Broder algorithm in a distributed setting is that it requires a very long random walk, i.e., a walk that covers the graph and might have to be Θ(mn) steps long for an n-vertex, m-edge graph, in the worst case. The most common technique for constructing random walks in "all-to-all" communication models such as CongestedClique and MPC are bottom-up techniques which start with many short walks and repeatedly stitch these together to build longer walks. These techniques fail to efficiently build the long random walk required by the Aldous-Broder algorithm. Our algorithm is a significant departure from known techniques, featuring a top-down walk filling approach paired with Schur complement graphs for walk shortcutting. To make this idea work in the CongestedClique model, we present a novel compressed random walk reconstruction algorithm, based on randomly sampling a weighted perfect matching. In addition, we show how to take somewhat shorter random walks even more efficiently in the CongestedClique model, obtaining an O (log3 n)-round algorithm for uniformly sampling spanning trees from graphs with O (n log n) cover times. These results are obtained by adding a load balancing component to the random walk algorithm of Bahmani, Chakrabarti and Xin (SIGMOD 2011) that uses the bottom-up "doubling" technique.
 Theory of computation -- Design and analysis of algorithms -- Distributed algorithms Theory of computation -- Randomness, geometry and discrete structures -- Random walks and Markov chains UIOWA OA Agreement

Details

Metrics

9 Record Views
Logo image