Fully Dynamic Effective Resistances
share
In this paper we consider the fully-dynamic All-Pairs Effective Resistance problem, where the goal is to maintain effective resistances on a graph G among any pair of query vertices under an intermixed sequence of edge insertions and deletions in G. The effective resistance between a pair of vertices is a physics-motivated quantity that encapsulates both the congestion and the dilation of a flow. It is directly related to random walks, and it has been instrumental in the recent works for designing fast algorithms for combinatorial optimization problems, graph sparsification, and network science. We give a data-structure that maintains (1+ϵ)-approximations to all-pair effective resistances of a fully-dynamic unweighted, undirected multi-graph G with Õ(m^4/5ϵ^-4) expected amortized update and query time, against an oblivious adversary. Key to our result is the maintenance of a dynamic Schur complement (also known as vertex resistance sparsifier) onto a set of terminal vertices of our choice. This maintenance is obtained (1) by interpreting the Schur complement as a sum of random walks and (2) by randomly picking the vertex subset into which the sparsifier is constructed. We can then show that each update in the graph affects a small number of such walks, which in turn leads to our sub-linear update time. We believe that this local representation of vertex sparsifiers may be of independent interest.
READ FULL TEXT