Algorithms and Complexity Seminar

Twice-Ramanujan Sparsifiers

Nikhil Srivastava (Yale University)

We prove that every graph has a spectral sparsifier with a number of edges linear in its number of vertices. As linear-sized spectral sparsifiers of complete graphs are expanders, our sparsifiers of arbitrary graphs can be viewed as generalizations of expander graphs.

In particular, we prove that for every d>1 and every undirected, weighted graph G = (V,E,w) on n vertices, there exists a weighted graph H=(V,F,w') with at most dn edges such that for every x in R^n,

x^T L_G x =< x^T L_H x =< (d+1+2sqrt(d) / d+1-2sqrt(d) ) x^T L_G x

where L_G and L_H are the Laplacian matrices of G and H, respectively. Thus, H approximates G spectrally at least as well as a Ramanujan expander with dn/2 edges approximates the complete graph. We give an elementary deterministic polynomial time algorithm for constructing H.

Joint work with Josh Batson and Dan Spielman.