Fast Generation of Random Spanning Trees and the Effective Resistance Metric

Abstract

We present a new algorithm for generating a uniformly random spanning tree in an undirected graph. Our algorithm samples such a tree in expected $\tilde{O}(m^{4/3})$ time. This improves over the best previously known bound of $\min (\tilde{O}(m\sqrt{n}),O(n^{\omega }))$ -- that follows from the work of Kelner and Mądry [FOCS'09] and of Colbourn et al. [J. Algorithms'96] -- whenever the input graph is sufficiently sparse. At a high level, our result stems from carefully exploiting the interplay of random spanning trees, random walks, and the notion of effective resistance, as well as from devising a way to algorithmically relate these concepts to the combinatorial structure of the graph. This involves, in particular, establishing a new connection between the effective resistance metric and the cut structure of the underlying graph.

References in corpus (1)

• Faster generation of random spanning trees

Cited by in corpus (8)

• Tree formulas, mean first passage times and Kemeny's constant of a Markov chain
• Runtime Analysis of Evolutionary Algorithms with Biased Mutation for the Multi-Objective Minimum Spanning Tree Problem
• Efficient Algorithms for Minimizing the Kirchhoff Index via Adding Edges
• Linking and Cutting Spanning Trees
• A Simple and Efficient Parallel Laplacian Solver
• A Matrix Chernoff Bound for Strongly Rayleigh Distributions and Spectral Sparsifiers from a few Random Spanning Trees
• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
• Sampling Random Spanning Trees Faster than Matrix Multiplication