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,Ẽ,w) of G such that |Ẽ| = O(n log n/ 2 ) and for all vectors 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.
The number of edges was later improved to O(n log n/ 2 ) by sampling every edge with probability proportional to its effective resistance REF .
Graph sparsification by effective resistances
STOC '08
Mathematics Computer Science