Partially-Dynamic All-Pairs Maxflow and Effective Resistance via Stable Sparsifiers

Abstract

We give a randomized data structure for undirected weighted graphs that are partially dynamic, i.e., that undergo either only edge insertions or only edge deletions. The data structure maintains $(1\pm \epsilon )$-approximations to the maxflow value and effective resistance between any queried pair of vertices, with total update time ${\tilde{O}}_{\epsilon }(n^2)$ and worst-case query time ${\tilde{O}}_{\epsilon }(1)$. Thus, for dense graphs where $m=\Omega (n^2)$, our guarantees are near-optimal. Our algorithms succeed with high probability against an adaptive adversary. Our result follows from a simple stability principle for partially dynamic graphs. We show how to partition an online sequence of $m$ updates into $\tilde{O}(n/\epsilon )$ epochs such that every graph within an epoch is a $(1\pm O(\epsilon ))$-spectral approximation of the graph at the beginning of the epoch. The epochs are determined by the cumulative leverage score of the updated edges: small leverage-score mass implies small spectral change, while the total leverage-score mass over a monotone update sequence is $\tilde{O}(n)$. Consequently, a spectral sparsifier needs to be recomputed only once per epoch. Applying known static all-pairs maxflow and effective-resistance oracles to these sparsifiers then yields the result.