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 ∈ R V (1 − ǫ) ∑ (x (u) − x (v) ) 2 wuv ≤ ∑ (x (u) − x (v) ) 2 ˜wuv ≤ (1 + ǫ) ∑ (x (u) − x (v) ) 2 wuv. (1) uv∈E uv ∈ ˜ E This improves upon the sparsifiers constructed by Spielman and Teng, which had O (n log c n) edges for some large constant c, and upon those of Benczúr and Karger, which only satisfied (1) for x ∈ 0, 1 V. 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. uv∈E