View article

We consider the problem of dynamically maintaining (approximate) all-pairs effective resistances in separable graphs, which are those that admit an -separator theorem for some . We give a fully dynamic algorithm that maintains -approximations of the all-pairs effective resistances of an -vertex graph undergoing edge insertions and deletions with worst-case update time and worst-case query time, if is guaranteed to be -separable (i.e., it is taken from a class satisfying a -separator theorem) and its separator can be computed in time. Our algorithm is built upon a dynamic algorithm for maintaining \emph{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 and , no incremental or decremental algorithm can maintain the effective resistance for -separable graphs with worst-case update time and query time for any , unless the Online Matrix Vector Multiplication (OMv) conjecture is false. We further show that for \emph{general} graphs, no incremental or decremental algorithm can maintain the effective resistance problem with worst-case update time and query-time for any , unless the OMv conjecture is false.