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

approximate Schur complementgraph sparsificationrandom spanning treessampling algorithm

Mathematics Subject Classification ID

Trees (05C05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) 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

(23)

• A queueing network-based distributed Laplacian solver
• Electrical flows over spanning trees
• Generating random spanning trees via fast matrix multiplication
• Random spanning trees and the prediction of weighted graphs
• Graph Clustering using Effective Resistance
• Density independent algorithms for sparsifying k-step random walks
• Dynamic effective resistances and approximate Schur complement on separable graphs
• The power of vertex sparsifiers in dynamic graph algorithms
• Determinant-preserving sparsification of SDDM matrices
• An almost-linear time algorithm for uniform random spanning tree generation
• Distance-Preserving Graph Contractions
• Fast generation of random spanning trees and the effective resistance metric
• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
• Models of random subtrees of a graph
• A BWT-based algorithm for random de Bruijn sequence construction
• A transient equivalence between Aldous-Broder and Wilson's algorithms and a two-stage framework for generating uniform spanning trees
• Better sparsifiers for directed Eulerian graphs
• Sampling random spanning arborescences in graphs with low conductance
• Optimal sublinear sampling of spanning trees and determinantal point processes via average-case entropic independence
• Nested dissection meets IPMs: planar min-cost flow in nearly-linear time
• Sparsification of the regularized magnetic Laplacian with multi-type spanning forests
• Sampling arborescences in parallel
• Faster min-cost flow and approximate tree decomposition on bounded treewidth graphs

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)