Thumbnail
Access Restriction
Open

Author Batson, Joshua ♦ Spielman, Daniel A. ♦ Srivastava, Nikhil
Source arXiv.org
Content type Text
File Format PDF
Date of Submission 2008-08-01
Language English
Subject Domain (in DDC) Computer science, information & general works
Subject Keyword Computer Science - Data Structures and Algorithms ♦ Computer Science - Discrete Mathematics ♦ cs
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,\tilde{w})$ with at most $\ceil{d(n-1)}$ edges such that for every $x \in \R^{V}$, \[ x^{T}L_{G}x \leq x^{T}L_{H}x \leq (\frac{d+1+2\sqrt{d}}{d+1-2\sqrt{d}})\cdot 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$.
Educational Use Research
Learning Resource Type Article


Open content in new tab

   Open content in new tab