2018/02/26 by Goranci, Gramoz, Henzinger, Monika, Peng, Pan · 1 citation
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.1802.09111
We consider the problem of dynamically maintaining (approximate) all-pairs effective resistances in separable graphs, which are those that admit an nc-separator theorem for some c<1. 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 O(√(n)/ε2) worst-case update time and O(√(n)/ε2) worst-case query time, if G is guaranteed to be √(n)-separable (i.e., it is taken from a class satisfying a √(n)-separator theorem) and its separator can be computed in O(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 complement our result by proving that for any two fixed vertices s and t, no incremental or decremental algorithm can maintain the s-t effective resistance for √(n)-separable graphs with worst-case update time O(n1/2-δ) and query time O(n1-δ) 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 the s-t effective resistance problem with worst-case update time O(n1-δ) and query-time O(n2-δ) for any δ>0, unless the OMv conjecture is false.