Graph Sparsification by Effective Resistances

DOI10.48550/ARXIV.0803.0929MaRDI QIDQ89551arXivFDO

Authors Daniel A. Spielman, Nikhil Srivastava

Publication date 6 March 2008

Abstract: 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

e p s i l o n > 0

, we produce a weighted subgraph

H = (V, i l d e E, i l d e w)

of

G

such that

| i l d e E | = O (n l o g n / e p s i l o n^{2})

and for all vectors

x i n R^{V}

(1 - e p s i l o n) s u m_{u v i n E} (x (u) - x (v))^{2} w_{u v} l e s u m_{u v i n i l d e E} (x (u) - x (v))^{2} i l d e w_{u v} l e (1 + e p s i l o n) s u m_{u v i n E} (x (u) - x (v))^{2} w_{u v} . (*)

This improves upon the sparsifiers constructed by Spielman and Teng, which had

O (n l o g^{c} n)

edges for some large constant

c

, and upon those of Bencz'ur and Karger, which only satisfied (*) for

x i n {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 (l o g n)

time.

Cited in

(1)

simplifyNet

This page was built for publication: Graph Sparsification by Effective Resistances

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q89551)