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

DOI10.1145/3188745.3188852MaRDI QIDQ5230291zbMATH OpenOpenAlexFDO

Authors Aaron Schild

Publication date 22 August 2019

Published in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.06455

zbMATH Keywords

random walksSchur complementsrandom spanning trees

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20) Signed and weighted graphs (05C22) Random walks on graphs (05C81)

Abstract: We give an $$-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)}epsilo{n}^{-o(1)}$-time algorithm for generating a random spanning tree with total variation distance $epsilon$ from the true uniform distribution. Our second algorithm's runtime does not depend on the edge weights. Our $$-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-Mk{a}dry and Mk{a}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.

Recommendations

• Generating random spanning trees via fast matrix multiplication
• Sampling random spanning trees faster than matrix multiplication
• Fast generation of random spanning trees and the effective resistance metric
• Non-uniform random spanning trees on weighted graphs
• scientific article; zbMATH DE number 1256746

Cited in

(24)

• A reverse Aldous-Broder algorithm
• Sparsification of the regularized magnetic Laplacian with multi-type spanning forests
• scientific article; zbMATH DE number 7378710 (Why is no real title available?)
• Generating random spanning trees via fast matrix multiplication
• Determinant-preserving sparsification of SDDM matrices
• Small-space spectral sparsification via bounded-independence sampling
• Sampling arborescences in parallel
• An exact method to generate all nondominated spanning trees
• Near-optimal two-pass streaming algorithm for sampling random walks over directed graphs
• Sampling random spanning trees faster than matrix multiplication
• Spectral sparsification via bounded-independence sampling
• On a wider class of prior distributions for graphical models
• Spectral Clustering, Bayesian Spanning Forest, and Forest Process
• Models of random subtrees of a graph
• A transient equivalence between Aldous-Broder and Wilson's algorithms and a two-stage framework for generating uniform spanning trees
• Optimal electrical oblivious routing on expanders
• Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis
• A Spectral Approach to Network Design
• Electrical flows for polylogarithmic competitive oblivious routing
• Optimal sublinear sampling of spanning trees and determinantal point processes via average-case entropic independence
• Exact sampling of spanning trees via fast-forwarded random walks
• Fast generation of random spanning trees and the effective resistance metric
• A queueing network-based distributed Laplacian solver
• On finding most uniform spanning trees

This page was built for publication: An almost-linear time algorithm for uniform random spanning tree generation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230291)