# An almost-linear time algorithm for uniform random spanning tree generation

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Nov 2017.

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

- [Optimal Sublinear Sampling of Spanning Trees and Determinantal Point Processes via Average-Case Entropic Independence](https://mlsanity.com/paper/2204.02570/) (2022)
- [The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure](https://mlsanity.com/paper/2312.04762/) (2023)
- [Sparsification of the regularized magnetic Laplacian with multi-type spanning forests](https://mlsanity.com/paper/2208.14797/) (2022)
- [Quantum Speedup for Spectral Approximation of Kronecker Products](https://mlsanity.com/paper/2402.07027/) (2024)
- [Binary Hypothesis Testing for Softmax Models and Leverage Score Models](https://mlsanity.com/paper/2405.06003/) (2024)
- [Quantifying Variational Approximation for the Log-Partition Function](https://mlsanity.com/paper/2102.10196/) (2021)

## Abstract (arXiv)

We give an m1+o(1)βo(1)-time algorithm for generating a uniformly random spanning tree in an undirected, weighted graph with max-to-min weight ratio β. We also give an m1+o(1)ε-o(1)-time algorithm for generating a random spanning tree with total variation distance ε from the true uniform distribution. Our second algorithm's runtime does not depend on the edge weights. Our m1+o(1)βo(1)-time algorithm is the first almost-linear time algorithm for the problem --- even on unweighted graphs --- and is the first subquadratic time algorithm for sparse weighted graphs. Our algorithms improve on the random walk-based approach given in Kelner-Mkadry and Mkadry-Straszak-Tarnawski. We introduce a new way of using Laplacian solvers to shortcut a random walk. In order to fully exploit this shortcutting technique, we prove a number of new facts about electrical flows in graphs. These facts seek to better understand sets of vertices that are well-separated in the effective resistance metric in connection with Schur complements, concentration phenomena for electrical flows after conditioning on partial samples of a random spanning tree, and more.