Twice-Ramanujan Sparsifiers

Опубликовано 18 августа 2016, 22:50

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,\tilde{w})$ with at most $dn $ edges such that for every $x \in \R^{V}$, \[ x^T L_G x \leq x^T L_H x \leq ( d+1+2\sqrt{d} / d+1-2\sqrt{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.