Faster generation of random spanning trees

Abstract

In this paper, we set forth a new algorithm for generating approximately uniformly random spanning trees in undirected graphs. We show how to sample from a distribution that is within a multiplicative $(1+\delta )$ of uniform in expected time $\TO(m\sqrt{n}\log 1/δ)$. This improves the sparse graph case of the best previously known worst-case bound of $O(\min \{mn,n^{2.376}\})$, which has stood for twenty years. To achieve this goal, we exploit the connection between random walks on graphs and electrical networks, and we use this to introduce a new approach to the problem that integrates discrete random walk-based techniques with continuous linear algebraic methods. We believe that our use of electrical networks and sparse linear system solvers in conjunction with random walks and combinatorial partitioning techniques is a useful paradigm that will find further applications in algorithmic graph theory.

References in corpus (1)

• Nearly-Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems

Cited by in corpus (6)

• Fast Generation of Random Spanning Trees and the Effective Resistance Metric
• A Fast Distributed Solver for Symmetric Diagonally Dominant Linear Equations
• Polynomial-Time Algorithms for Submodular Laplacian Systems
• Acyclic Orientations and Spanning Trees
• Improved bounds on the sandpile diffusions on Grid graphs
• Efficient Distributed Random Walks with Applications