Sampling random spanning trees faster than matrix multiplication
Open Access
- 19 June 2017
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 730-742
Abstract
We present an algorithm that, with high probability, generates a random spanning tree from an edge-weighted undirected graph in (n5/3 m1/3) time. The tree is sampled from a distribution where the probability of each tree is proportional to the product of its edge weights. This improves upon the previous best algorithm due to Colbourn et al. that runs in matrix multiplication time, O(nω). For the special case of unweighted graphs, this improves upon the best previously known running time of Õ(min{nω,m√n,m4/3}) for m ⪢ n7/4 (Colbourn et al. '96, Kelner-Madry '09, Madry et al. '15). The effective resistance metric is essential to our algorithm, as in the work of Madry et al., but we eschew determinant-based and random walk-based techniques used by previous algorithms. Instead, our algorithm is based on Gaussian elimination, and the fact that effective resistance is preserved in the graph resulting from eliminating a subset of vertices (called a Schur complement). As part of our algorithm, we show how to compute -approximate effective resistances for a set S of vertex pairs via approximate Schur complements in Õ(m+(n + |S|)ε-2) time, without using the Johnson-Lindenstrauss lemma which requires Õ( min{(m + |S|)ε2, m+nε-4 +|S|ε2}) time. We combine this approximation procedure with an error correction procedure for handling edges where our estimate isn't sufficiently accurate.Keywords
All Related Versions
Funding Information
- National Science Foundation (1065125)
- ONR Award (N00014-16-1-2374)
- National Science Foundation Graduate Research Fellowship (1122374)
This publication has 17 references indexed in Scilit:
- Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear SystemsSIAM Journal on Matrix Analysis and Applications, 2014
- Approaching Optimality for Solving SDD Linear SystemsSIAM Journal on Computing, 2014
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear time2013
- Graph Sparsification by Effective ResistancesSIAM Journal on Computing, 2011
- An O(log n/log log n)-approximation Algorithm for the Asymmetric Traveling Salesman Problem2010
- Two Algorithms for Unranking ArborescencesJournal of Algorithms, 1996
- The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled TreesSIAM Journal on Discrete Mathematics, 1990
- Generating random combinatorial objectsJournal of Algorithms, 1990
- Unranking and ranking spanning trees of a graphJournal of Algorithms, 1989
- Random spanning treeJournal of Algorithms, 1983