Partially-Dynamic All-Pairs Maxflow and Effective Resistance via Stable Sparsifiers
2026-08-26 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors created a randomized method to quickly keep track of approximate maxflow values and effective resistance between any two points in a graph that is either only growing or only shrinking (by edges). Their technique works very efficiently, especially for dense graphs, by splitting updates into groups where the graph doesn't change much in a certain mathematical sense. They use a concept called leverage scores to decide when to update a simpler version of the graph, which makes querying these properties fast and accurate. This approach works with high reliability even if changes are made in a tricky, adaptive way.
undirected weighted graphspartially dynamic graphsmaxfloweffective resistancespectral approximationleverage scoresspectral sparsifierrandomized data structuresadaptive adversary
Authors
Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg, Yibin Zhao, Gernot Zöcklein
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ε)$-approximations to the maxflow value and effective resistance between any queried pair of vertices, with total update time $\widetilde{O}_ε(n^2)$ and worst-case query time $\widetilde{O}_ε(1)$. Thus, for dense graphs where $m = Ω(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 $\widetilde{O}(n/ε)$ epochs such that every graph within an epoch is a $(1\pm O(ε))$-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 $\widetilde{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.