Twice-Ramanujan Sparsifiers
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2008
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914816736624640 |
|---|---|
| author | Batson, Joshua Spielman, Daniel A. Srivastava, Nikhil |
| author_facet | Batson, Joshua Spielman, Daniel A. Srivastava, Nikhil |
| contents | 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 $\lceil d(n-1) \rceil$ edges such that for every $x \in \mathbb{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$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_0808_0163 |
| institution | arXiv |
| publishDate | 2008 |
| record_format | arxiv |
| spellingShingle | Twice-Ramanujan Sparsifiers Batson, Joshua Spielman, Daniel A. Srivastava, Nikhil Data Structures and Algorithms Discrete Mathematics 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 $\lceil d(n-1) \rceil$ edges such that for every $x \in \mathbb{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$. |
| title | Twice-Ramanujan Sparsifiers |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/0808.0163 |