{"id":"arxiv:1711.06455","kind":"preprint","title":"An almost-linear time algorithm for uniform random spanning tree generation","authors":["Aaron Schild"],"author_count":1,"year":2017,"published":"2017-11-17","venue":null,"cited_by":null,"doi":null,"arxiv_id":"1711.06455","nct_id":null,"source_url":"https://arxiv.org/abs/1711.06455","archive_url":"https://space-kitty.com/papers/arxiv:1711.06455","updated":"2017-11-17","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/1711.06455","abstract":"We give an $m^{1+o(1)}β^{o(1)}$-time algorithm for generating a uniformly random spanning tree in an undirected, weighted graph with max-to-min weight ratio $β$. We also give an $m^{1+o(1)}ε^{-o(1)}$-time algorithm for generating a random spanning tree with total variation distance $ε$ from the true uniform distribution. Our second algorithm's runtime does not depend on the edge weights. Our $m^{1+o(1)}β^{o(1)}$-time algorithm is the first almost-linear time algorithm for the problem --- even on unweighted graphs --- and is the first subquadratic time algorithm for sparse weighted graphs. Our algorithms improve on the random walk-based approach given in Kelner-Mądry and Mądry-Straszak-Tarnawski. We introduce a new way of using Laplacian solvers to shortcut a random walk. In order to fully exploit this shortcutting technique, we prove a number of new facts about electrical flows in graphs. These facts seek to better understand sets of vertices that are well-separated in the effective resistance metric in connection with Schur complements, concentration phenomena for electrical flows after conditioning on partial samples of a random spanning tree, and more.","abstract_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS","cs.DM","math.PR"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}