An almost-linear time algorithm for uniform random spanning tree generation
share
We give an m^1+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 m^1+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 m^1+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-Mądry and Mądry-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.
READ FULL TEXT