Twice-Ramanujan Sparsifiers

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 d(n-1) edges such that for every xV, xTLGx≤ xTLHx≤(d+1+2√dd+1-2√d)· xTLGx, where LG and LH 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.