PaperlayerView exact revision on arXiv

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

arXiv:2608.26037v1cs.DS

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.

    Source: §1 · p. 2

  • Method

    The method partitions monotone updates into spectrally stable epochs, maintains an adaptive sparsifier, and invokes static all-pairs oracles when the sparsifier changes.

    Source: §3.1 · p. 5

  • 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.

    Source: §1 · p. 3

  • 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.

    Source: §1 · p. 3

    The dependence on ε−1 is larger than in corresponding fixed-pair results, and improving it remains an open problem.

    Source: §1 · p. 3

Abstract

from arXiv · show

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.Source: §1 · p. 2
  • Partially dynamic all-pairs maxflow and effective-resistance maintenance had no known improvement beyond fully dynamic algorithms.Source: §1 · p. 2

Our contribution

  • The data structure maintains (1 ± ε)-approximations for all-pairs maxflow values and effective resistances in eOε(n2) total update time.Source: §1 · p. 3
  • Each query takes worst-case eO(1/ε2) time, and the guarantees hold with high probability against an adaptive adversary.Source: §1 · p. 3
  • The result supports arbitrary pairs, is near-optimal for dense monotone sequences, and improves the eOε(mn) baseline when m = ω(n).Source: §1 · p. 3

Limitations

  • The paper identifies the dependence on ε−1 as larger than in corresponding fixed-pair results and leaves improving it as an open problem.Source: §1 · p. 3

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).Source: §1 · p. 3

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.Source: §2 · p. 3
  • Effective resistance between vertices is defined through the Laplacian pseudoinverse and represents the electrical energy required to route one unit of flow.Source: §2 · pp. 3–4
  • A spectral sparsifier H approximates G when their Laplacians satisfy (1−ε)L_G ⪯ L_H ⪯ (1+ε)L_G.Source: §2 · p. 4
  • 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.Source: §2 · p. 4

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.Source: §3.1 · pp. 4–5

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.Source: §3.1 · p. 4

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.Source: §3.1 · p. 4

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.Source: The Algorithm · p. 6

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.Source: The Algorithm · pp. 6–7
Loading 2608.26037v1…