A new theoretical algorithm is designed to keep answering two demanding questions about a changing network: how much flow can pass between any two vertices, and how strongly those vertices are connected in electrical terms. The method handles graphs that only gain edges or only lose them, and returns a (1 ± ε)-approximation for both quantities for every queried pair. Here, ε is the chosen accuracy parameter and lies between 0 and 1.
The work’s central idea is to avoid rebuilding the algorithm’s compact view of the graph after every update. Instead, it groups the update stream into stable epochs—periods in which cumulative leverage-score mass remains small—and reuses one spectral sparsifier across the graph versions in each epoch. The authors report high-probability guarantees even when an adaptive adversary, such as an update chooser reacting to earlier outputs, controls the sequence.
A compact summary of the changing graph
A spectral sparsifier is a weighted graph that preserves the current graph spectrally while using O(n/ε³) edges. The maintenance procedure changes the sparsifier at O(n/ε) update steps and has total maintenance time O(n²/ε⁴), according to the stated bound.
The reuse rule tracks leverage-score mass, the quantity used in the analysis to measure structural change. When little leverage-score mass changes, the algorithm keeps the old sparsifier; when the accumulated change becomes large, it implicitly resamples the sparsifier. The previous sparsifier remains available for the next leverage-score calculation, while its resistance estimate has (1 ± ε/10) accuracy and the maintained invariant is that H(t) is an ε/4-spectral approximation of G(t).
The stability analysis gives the update stream a global budget: total leverage-score mass is O(n), which supports O(n/ε) stable epochs, with one sparsifier recomputation per epoch. It also bounds the number of reinitializations of H by O(n log n/ε). In the stated analysis, the compact representation can therefore be reused across multiple updates before it is recomputed.
What the reported bounds promise
On top of the maintained sparsifier, the main randomized data structure supports arbitrary vertex-pair queries with the stated worst-case query and total-update bounds. The supplied theorem gives query time with ε exponent 2 and total update time with n exponent 2 and ε exponent 7, up to asymptotic factors suppressed in the paper’s presentation.
The construction draws on static all-pairs oracles. The cited resistance oracle returns (1 ± ε)-accurate answers with high probability, with displayed construction and query factors involving log(1/ε)/ε² and 1/ε². The cited maxflow oracle has construction time O(m/ε³), constant query time, and the same multiplicative accuracy with high probability.
The authors describe the result as matching the O(n²) total-update bound for a fixed vertex pair while answering arbitrary pairs. They also report that it is near-optimal for dense monotone sequences, where m = Θ(n²), and improves on the cited Oε(mn) baseline when m = ω(n). These are asymptotic comparisons with cited algorithmic bounds, not independently reproduced benchmark results.
The result’s boundaries
The analysis concerns theoretical undirected weighted graphs with positive polynomially bounded edge weights. It covers insertion-only sequences or deletion-only sequences, with ε between 0 and 1, rather than streams that freely mix both kinds of update. The guarantees are randomized and hold with high probability against an adaptive adversary; the supplied analysis does not report an explicit failure probability.
The supplied performance claims are asymptotic bounds, and the dense-regime comparison is an authors’ comparison with cited baselines rather than an independently reproduced benchmark. The answers are approximations when ε is nonzero, and the randomized structure does not provide a deterministic guarantee.
Paper data and sources
Original title: Partially-Dynamic All-Pairs Maxflow and Effective Resistance via Stable Sparsifiers
Authors: Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg et al.
Journal/Repository: arXiv
Status: Preprint, not yet peer-reviewed
First online: 2026-08-26
DOI: Not available
Original paper · Full text