Sampling random spanning trees faster than matrix multiplication

DOI10.1145/3055399.3055499zbMATH Open1370.68122arXiv1611.07451OpenAlexW2552685338MaRDI QIDQ4978019FDOQ4978019

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)

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.

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

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

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)

Cited In (16)

• Electrical flows over spanning trees
• Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
• Distance-Preserving Graph Contractions
• Title not available (Why is that?)
• 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
• A transient equivalence between Aldous-Broder and Wilson's algorithms and a two-stage framework for generating uniform spanning trees
• Random spanning trees and the prediction of weighted graphs
• Density independent algorithms for sparsifying \(k\)-step random walks
• Fast generation of random spanning trees and the effective resistance metric
• A BWT-based algorithm for random de Bruijn sequence construction
• A queueing network-based distributed Laplacian solver
• 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)