Graph Sparsification by Effective Resistances

We present a nearly linear time algorithm that produces high-quality spectral sparsifiers of weighted graphs. Given as input a weighted graph $G=(V,E,w)$ and a parameter $epsilon>0$, we produce a weighted subgraph $H=(V,tilde{E},tilde{w})$ of G such that $|tilde{E}|=O(nlog n/epsilon^2)$ and all $xinmathbb{R}^V$ satisfy $(1-epsilon)sum_{uvin E},(x(u)-x(v))^2w_{uv}leqsum_{uvintilde{E}},(x(u)-x(v))^2tilde{w}_{uv}leq(1+epsilon)sum_{uvin E},(x(u)-x(v))^2w_{uv}$. This improves upon the spectral sparsifiers constructed by Spielman and Teng, which had $O(nlog^{c}n)$ edges for some large constant c, and upon the cut sparsifiers of Benczúr and Karger, which only satisfied these inequalities for $xin{0,1}^V$. A key ingredient in our algorithm is a subroutine of independent interest: a nearly linear time algorithm that builds a data structure from which we can query the approximate effective resistance between any two vertices in a graph in $O(log n)$ time.