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, (E) over tilde, (w) over tilde) of G such that |(E) over tilde| = O(n log n/epsilon(2)) and all x is an element of R-V satisfy (1 - epsilon)Sigma(uv is an element of E) (x(u) - x(v))(2)w(uv) <= Sigma(uv is an element of(E) over tilde) (x(u) - x(v))(2)(w) over tilde (uv) <= (1 + epsilon) Sigma(uv is an element of E) (x(u) -x(v))(2)w(uv). This improves upon the spectral sparsifiers constructed by Spielman and Teng, which had O(n log(c) n) edges for some large constant c, and upon the cut sparsifiers of Benczur and Karger, which only satisfied these inequalities for x. {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.