Graph sparsification by effective resistances

We present a nearly-linear time algorithm that produces high-quality sparsifiers of weighted graphs. Given as input a weighted graph G= (V, E, w) and a parameter ε>0, we produce a weighted subgraph H= (V, ~E, ~w) of G such that |~E|=O (n log n/ε2) and for all vectors x in RV. (1-ε) ∑uv ∈ E (x (u) -x (v) ) 2wuv≤ ∑uv in ~E (x (u) -x (v) ) 2~wuv ≤ (1+ε) ∑uv ∈ E (x (u) -x (v) ) 2wuv. This improves upon the sparsifiers constructed by Spielman and Teng, which had O (n logc n) edges for some large constant c, and upon those of Benczur and Karger, which only satisfied (1) for x in 0, 1V. We conjecture the existence of sparsifiers with O (n) edges, noting that these would generalize the notion of expander graphs, which are constant-degree sparsifiers for the complete graph. 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.