Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees
Preprint
Abstract
We show variants of spectral sparsification routines can preserve the total spanning tree counts of graphs, which by Kirchhoff's matrix-tree theorem, is equivalent to determinant of a graph Laplacian minor, or equivalently, of any SDDM matrix. Our analyses utilizes this combinatorial connection to bridge between statistical leverage scores / effective resistances and the analysis of random graphs by [Janson, Combinatorics, Probability and Computing `94]. This leads to a routine that in quadratic time, sparsifies a graph down to about $n^{1.5}$ edges in ways that preserve both the determinant and the distribution of spanning trees (provided the sparsified graph is viewed as a random object). Extending this algorithm to work with Schur complements and approximate Choleksy factorizations leads to algorithms for counting and sampling spanning trees which are nearly optimal for dense graphs. We give an algorithm that computes a $(1 \pm \delta)$ approximation to the determinant of any SDDM matrix with constant probability in about $n^2 \delta^{-2}$ time. This is the first routine for graphs that outperforms general-purpose routines for computing determinants of arbitrary matrices. We also give an algorithm that generates in about $n^2 \delta^{-2}$ time a spanning tree of a weighted undirected graph from a distribution with total variation distance of $\delta$ from the $w$-uniform distribution .
Keywords
All Related Versions
This publication has 8 references indexed in Scilit:
- A randomized algorithm for approximating the log determinant of a symmetric positive definite matrixLinear Algebra and its Applications, 2017
- Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear SystemsSIAM Journal on Matrix Analysis and Applications, 2014
- User-Friendly Tail Bounds for Sums of Random MatricesFoundations of Computational Mathematics, 2011
- Graph Sparsification by Effective ResistancesSIAM Journal on Computing, 2011
- Maintaining information in fully dynamic trees with top treesACM Transactions on Algorithms, 2005
- Sparsification—a technique for speeding up dynamic graph algorithmsJournal of the ACM, 1997
- The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random GraphCombinatorics, Probability and Computing, 1994
- Random spanning treeJournal of Algorithms, 1983