2026-07-23T20:57:01Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9503 2024-03-06T10:43:54Z ddc:004 open_access

Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs Goranci, Gramoz Henzinger, Monika Peng, Pan Dynamic graph algorithms effective resistance separable graphs Schur complement conditional lower bounds We consider the problem of dynamically maintaining (approximate) all-pairs 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 all-pairs effective resistances of an n-vertex graph G undergoing edge insertions and deletions with O~(sqrt{n}/epsilon^2) worst-case update time and O~(sqrt{n}/epsilon^2) worst-case 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 s-t effective resistance for sqrt{n}-separable graphs with worst-case update time O(n^{1/2-delta}) and query time O(n^{1-delta}) 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 s-t effective resistance problem with worst-case update time O(n^{1-delta}) and query-time O(n^{2-delta}) for any delta >0, unless the OMv conjecture is false. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gramoz Goranci and Monika Henzinger and Pan Peng 2018 Is Part Of LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2018.40 urn:nbn:de:0030-drops-95036 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.40 eng https://creativecommons.org/licenses/by/3.0/legalcode