Abstract
We show variants of spectral sparsification routines can preserve the total spanning tree counts of graphs. By Kirchhoff’s matrix-tree theorem, this quantity is the determinant of a graph Laplacian minor, or equivalently, of any SDDM matrix. Our analyses utilize 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 Cholesky factorizations leads to algorithms for counting and sampling spanning trees which are nearly optimal for dense graphs.
Joint with David Durfee, John Peebles, and Anup B. Rao, manuscript available at https://arxiv.org/abs/1705.00985.
Time
2017-05-17 14:00 ~ 15:00Speaker
Richard Peng, Georgia Institute of TechnologyRoom
Room 308,School of Information Management & Engineering, Shanghai University of Finance & Economics
