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 ∈ RV, xT LG x ≤ xT LH x ≤ ((d+1+2√d)/(d+1-2√d)) • xT LG x 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.
%0 Conference Paper
%1 batson09
%A Batson, Joshua D.
%A Spielman, Daniel A.
%A Srivastava, Nikhil
%B Proceedings of the 41st annual ACM symposium on Theory of computing
%C New York, NY, USA
%D 2009
%I ACM
%K characteristic courant-fischer eigenvalues expander graph.theory laguerre linear.algebra matrix ramanujan sparsification spectral_graph_theory
%P 255--262
%R 10.1145/1536414.1536451
%T Twice-Ramanujan Sparsifiers
%X 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 ∈ RV, xT LG x ≤ xT LH x ≤ ((d+1+2√d)/(d+1-2√d)) • xT LG x 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.
%@ 978-1-60558-506-2
@inproceedings{batson09,
abstract = {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 ∈ RV, [xT LG x ≤ xT LH x ≤ ((d+1+2√d)/(d+1-2√d)) • xT LG x] 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.},
acmid = {1536451},
added-at = {2011-03-28T23:21:08.000+0200},
address = {New York, NY, USA},
author = {Batson, Joshua D. and Spielman, Daniel A. and Srivastava, Nikhil},
biburl = {https://www.bibsonomy.org/bibtex/24a70d1be2be6686ed5cb53eb1c00b82f/ytyoun},
booktitle = {Proceedings of the 41st annual ACM symposium on Theory of computing},
doi = {10.1145/1536414.1536451},
interhash = {ca9aed22962c62ca09a2eaf38cc9423e},
intrahash = {4a70d1be2be6686ed5cb53eb1c00b82f},
isbn = {978-1-60558-506-2},
keywords = {characteristic courant-fischer eigenvalues expander graph.theory laguerre linear.algebra matrix ramanujan sparsification spectral_graph_theory},
location = {Bethesda, MD, USA},
numpages = {8},
pages = {255--262},
publisher = {ACM},
series = {STOC '09},
timestamp = {2016-10-20T13:29:43.000+0200},
title = {Twice-{Ramanujan} Sparsifiers},
year = 2009
}