Source-linked AI summary
Partially-Dynamic All-Pairs Maxflow and Effective Resistance via Stable Sparsifiers
Gramoz Goranci, Rasmus Kyng, Maximilian Probst Gutenberg, Yibin Zhao, Gernot Zöcklein
TL;DR
Dynamic maintenance of approximate all-pairs maxflow and effective-resistance oracles is less developed than fixed-pair maintenance. The paper uses stable spectral sparsifiers across monotone-update epochs, achieving near-quadratic total update time with arbitrary-pair queries and adaptive-adversary guarantees.
Problem
The paper studies how to efficiently maintain approximate all-pairs maxflow and effective-resistance oracles in dynamically updated graphs.
Method
The method partitions monotone updates into spectrally stable epochs, maintains an adaptive sparsifier, and invokes static all-pairs oracles when the sparsifier changes.
Results
The data structure achieves eOε(n2) total update time, worst-case eO(1/ε2) query time, and high-probability guarantees against an adaptive adversary for both quantities.
Takeaways & Limitations
The result supports arbitrary-pair queries while matching the eOε(n2) update time of fixed-pair algorithms and is near-optimal for dense monotone update sequences.
Takeaways & Limitations
The dependence on ε−1 is larger than in corresponding fixed-pair results, and improving it remains an open problem.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper addresses maintaining approximate all-pairs maxflow and effective-resistance oracles in partially dynamic graphs, where prior improvements were mainly for fixed vertex pairs. It achieves near-quadratic total update time with arbitrary-pair queries by exploiting monotonicity through stable spectral sparsifiers.
- Dynamic algorithms: Exact dynamic maxflow is conditionally difficult, motivating (1 ± ε)-approximations for undirected graphs.An OMv-based lower bound rules out O(n^(1−δ)) amortized update time even for fixed-pair partially dynamic weighted graphs.
- Dynamic algorithms: Partially dynamic all-pairs maxflow and effective-resistance maintenance had no known improvement beyond fully dynamic algorithms.
- Our contribution: The data structure maintains (1 ± ε)-approximations for all-pairs maxflow values and effective resistances in eOε(n2) total update time.
- Our contribution: Each query takes worst-case eO(1/ε2) time, and the guarantees hold with high probability against an adaptive adversary.
- Our contribution: The result supports arbitrary pairs, is near-optimal for dense monotone sequences, and improves the eOε(mn) baseline when m = ω(n).
- Limitations: The paper identifies the dependence on ε−1 as larger than in corresponding fixed-pair results and leaves improving it as an open problem.
- Our approach: The approach partitions updates into eO(n/ε) epochs whose graphs remain spectrally close, allowing sparsifier and static-oracle rebuilding only at epoch boundaries.Epoch boundaries are determined by cumulative leverage-score mass; total mass over monotone updates is bounded by O(n log n).
2 Preliminaries
The preliminaries define effective resistance and spectral sparsification through graph Laplacians and establish why sparsifiers preserve both effective resistance and maxflow values. This observation enables static-oracle methods to operate on sparse approximations.
- The graph Laplacian is defined from oriented edge incidence vectors b_e = 1_v − 1_u and edge weights.
- Effective resistance between vertices is defined through the Laplacian pseudoinverse and represents the electrical energy required to route one unit of flow.
- A spectral sparsifier H approximates G when their Laplacians satisfy (1−ε)L_G ⪯ L_H ⪯ (1+ε)L_G.
- A (1 ± ε)-spectral sparsifier preserves both effective resistances and maxflow values within a (1 ± ε) factor.For maxflow, spectral approximation preserves cuts, and the maxflow-mincut theorem transfers that guarantee to flow values.
3 The Algorithm
The algorithm maintains an adaptive spectral sparsifier that changes only at a small number of update steps, allowing static all-pairs maxflow and effective-resistance oracles to be rebuilt sparingly. Leverage-score estimates and spectral stability ensure the sparsifier remains accurate throughout partially dynamic updates.
- Reducing queries to static oracles: A sparsifier change triggers static all-pairs effective-resistance and maxflow oracle construction, after which queries take near-constant time.Spectral sparsification preserves maxflow values through cut preservation and the maxflow-mincut theorem; effective resistances use static Laplacian-solve-based oracles.
- Adaptive sparsifier maintenance: eO(n/ε) update steps suffice for maintaining H, which remains a (1±ε)-spectral approximation of the current graph.The guarantee holds with high probability against an adaptive adversary.
- Scope of the guarantee: The sparsifier may change by arbitrarily many edges at one update step, so a bound on change steps is weaker than a bound on total edge changes.This distinction does not affect the application described here.
- Leverage-score triggering: The algorithm keeps the old sparsifier when cumulative leverage-score mass is small and implicitly resamples it when that mass becomes large.Incremental updates use online leverage scores, while decremental updates use reverse online leverage scores.
- Stability analysis: eO(n/ε) reinitializations follow from stability: small leverage-score mass implies small spectral change, and monotonicity handles both insertion and deletion sequences.Within an interval where H is unchanged, graph versions remain close by transitivity of spectral approximation.