Sampling random spanning trees faster than matrix multiplication

DOI10.1145/3055399.3055499MaRDI QIDQ4978019zbMATH OpenOpenAlexFDO

Authors David Durfee, Rasmus Kyng, John Peebles, Sushant Sachdeva, Anup B. Rao

Publication date 17 August 2017

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

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

zbMATH Keywords

random spanning treessampling algorithmapproximate Schur complementgraph sparsification

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Abstract: We present an algorithm that, with high probability, generates a random spanning tree from an edge-weighted undirected graph in $ildeO(n^{4/3}{m}^{1/2}+n^2)$ time (The $ildeO(cdot)$ notation hides $operatornamepolylog(n)$ factors). 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^{o}mega)$. For the special case of unweighted graphs, this improves upon the best previously known running time of $ildeO(min{n}^{omega},msqrtn,m^{4/3})$ for $mgg{n}^{5/3}$ (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 $epsilon$-approximate effective resistances for a set $S$ of vertex pairs via approximate Schur complements in $ildeO(m+(n+|S|)epsilo{n}^{-2})$ time, without using the Johnson-Lindenstrauss lemma which requires $ildeO(min(m+|S|)epsilo{n}^{-2},m+nepsilo{n}^{-4}+|S|epsilo{n}^{-2})$ time. We combine this approximation procedure with an error correction procedure for handing edges where our estimate isn't sufficiently accurate.

Recommendations

• Fast generation of random spanning trees and the effective resistance metric
• Generating random spanning trees via fast matrix multiplication
• An almost-linear time algorithm for uniform random spanning tree generation
• scientific article; zbMATH DE number 1256746
• Graph sparsification by effective resistances

Cited in

(16)

• Electrical flows over spanning trees
• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
• Distance-Preserving Graph Contractions
• 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
• Graph Clustering using Effective Resistance
• The power of vertex sparsifiers in dynamic graph algorithms
• Models of random subtrees of a graph
• Random spanning trees and the prediction of weighted graphs
• A transient equivalence between Aldous-Broder and Wilson's algorithms and a two-stage framework for generating uniform spanning trees
• Density independent algorithms for sparsifying \(k\)-step random walks
• Fast generation of random spanning trees and the effective resistance metric
• A queueing network-based distributed Laplacian solver
• A BWT-based algorithm for random de Bruijn sequence construction
• An almost-linear time algorithm for uniform random spanning tree generation

This page was built for publication: Sampling random spanning trees faster than matrix multiplication

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