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 x ? R V , [x T L G x ? x T L H x ? ((d+1+2?d)/(d+1-2?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.
expander graphs spectral graph theory