Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs
share
We consider the problem of dynamically maintaining (approximate) all-pairs effective resistances in separable graphs, which are those that contain small balanced separators. We give a fully dynamic algorithm that maintains (1+ε)-approximations of the all-pairs effective resistances of an n-vertex graph G undergoing edge insertions and deletions with Õ(√(n)/ε^2) worst-case update time and Õ(√(n)/ε^2) worst-case query time, if G is guaranteed to be O(√(n))-separable (i.e., admit a balanced separator of size O(√(n))) and its separator can be computed in Õ(n) time. Our algorithm is built upon a dynamic algorithm for maintaining approximate Schur complement that approximately preserves pairwise effective resistances among a set of terminals for separable graphs, which might be of independent interest. We also show that our algorithm is close to optimal by proving that for any two fixed vertices s and t, there is no incremental or decremental (and thus, also no fully dynamic) algorithm that (1+O(1/n^36))-approximates the s-t effective resistance for O(√(n))-separable graphs with worst-case update time O(n^1/2-δ) and query time O(n^1-δ) for any δ>0, unless the Online Matrix Vector Multiplication (OMv) conjecture is false. We further show that for general graphs, no incremental or decremental algorithm can maintain a (1+O(1/n^20))-approximation of the s-t effective resistance with worst-case update time O(n^1-δ) and query-time O(n^2-δ) for any δ >0, unless the OMv conjecture is false.
READ FULL TEXT
