Goranci, Gramoz ;
Henzinger, Monika ;
Peng, Pan
Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs
Abstract
We consider the problem of dynamically maintaining (approximate) allpairs effective resistances in separable graphs, which are those that admit an n^{c}separator theorem for some c<1. We give a fully dynamic algorithm that maintains (1+epsilon)approximations of the allpairs effective resistances of an nvertex graph G undergoing edge insertions and deletions with O~(sqrt{n}/epsilon^2) worstcase update time and O~(sqrt{n}/epsilon^2) worstcase query time, if G is guaranteed to be sqrt{n}separable (i.e., it is taken from a class satisfying a sqrt{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 st effective resistance for sqrt{n}separable graphs with worstcase update time O(n^{1/2delta}) and query time O(n^{1delta}) for any delta>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 st effective resistance problem with worstcase update time O(n^{1delta}) and querytime O(n^{2delta}) for any delta >0, unless the OMv conjecture is false.
BibTeX  Entry
@InProceedings{goranci_et_al:LIPIcs:2018:9503,
author = {Gramoz Goranci and Monika Henzinger and Pan Peng},
title = {{Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs}},
booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)},
pages = {40:140:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770811},
ISSN = {18688969},
year = {2018},
volume = {112},
editor = {Yossi Azar and Hannah Bast and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9503},
URN = {urn:nbn:de:0030drops95036},
doi = {10.4230/LIPIcs.ESA.2018.40},
annote = {Keywords: Dynamic graph algorithms, effective resistance, separable graphs, Schur complement, conditional lower bounds}
}
14.08.2018
Keywords: 

Dynamic graph algorithms, effective resistance, separable graphs, Schur complement, conditional lower bounds 
Seminar: 

26th Annual European Symposium on Algorithms (ESA 2018)

Issue date: 

2018 
Date of publication: 

14.08.2018 