2024/11/20 by Sriram V. Pemmaraju, Pemmaraju, Sriram V., Sourya Roy +3 · 1 citation
Computer Science · Engineering · Physics and Astronomy · #Advanced Optical Network Technologies #Complex Network Analysis Techniques #Distributed #F.2.2 #FOS: Computer and information sciences #Network Traffic and Congestion Control #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2411.13334
openalex publication_date 2024/11/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \TildeO(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 \TildeO(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 \TildeO(n2/3+α) = O(n.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. 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(nlog 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.