Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees (Richard Peng)

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:00   

Speaker

Richard Peng, Georgia Institute of Technology

Room

Room 308,School of Information Management & Engineering, Shanghai University of Finance & Economics