# Sampling Random Spanning Trees Faster than Matrix Multiplication

arXiv: https://arxiv.org/abs/1611.07451 · HTML: https://mlsanity.com/paper/1611.07451/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Nov 2016.

## Built on by (most cited first, 7 of 7)

- [Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence](https://mlsanity.com/paper/2204.02570/) (2022)
- [Mixtures of All Trees](https://mlsanity.com/paper/2302.14202/) (2023)
- [Unbiased and Efficient Sampling of Dependency Trees](https://mlsanity.com/paper/2205.12621/) (2022)
- [Sparsification of the regularized magnetic Laplacian with multi-type spanning forests](https://mlsanity.com/paper/2208.14797/) (2022)
- [Randomized Schur Complement Views for Graph Contrastive Learning](https://mlsanity.com/paper/2306.04004/) (2023)
- [Collapsed Effective Operators for Higher-order Structures](https://mlsanity.com/paper/2606.23517/) (2026)
- [CAST: Canonical Approximate Schur Tree for Approximate Cholesky on Graphs](https://mlsanity.com/paper/2609.09255/) (2026)

## Abstract (arXiv)

We present an algorithm that, with high probability, generates a random spanning tree from an edge-weighted undirected graph in tildeO(n4/3m1/2+n2) time (The tildeO(·) notation hides operatornamepolylog(n) factors). The tree is sampled from a distribution where the probability of each tree is proportional to the product of its edge weights. This improves upon the previous best algorithm due to Colbourn et al. that runs in matrix multiplication time, O(nω). For the special case of unweighted graphs, this improves upon the best previously known running time of tildeO(minnω,m√n,m4/3) for m gg n5/3 (Colbourn et al. '96, Kelner-Madry '09, Madry et al. '15). The effective resistance metric is essential to our algorithm, as in the work of Madry et al., but we eschew determinant-based and random walk-based techniques used by previous algorithms. Instead, our algorithm is based on Gaussian elimination, and the fact that effective resistance is preserved in the graph resulting from eliminating a subset of vertices (called a Schur complement). As part of our algorithm, we show how to compute ε-approximate effective resistances for a set S of vertex pairs via approximate Schur complements in tildeO(m+(n + |S|)ε-2) time, without using the Johnson-Lindenstrauss lemma which requires tildeO( min(m + |S|)ε-2, m+nε-4 +|S|ε-2) time. We combine this approximation procedure with an error correction procedure for handing edges where our estimate isn't sufficiently accurate.