# Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time

arXiv: https://arxiv.org/abs/2311.03174 · HTML: https://mlsanity.com/paper/2311.03174/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Nov 2023.

## Built on by (most cited first, 1 of 1)

- [Hierarchical Forecast Reconciliation on Networks: A Network Flow Optimization Formulation](https://mlsanity.com/paper/2505.03955/) (2025)

## Abstract (arXiv)

We provide an algorithm which, with high probability, maintains a (1-ε)-approximate maximum flow on an undirected graph undergoing m-edge additions in amortized mo(1) ε-3 time per update. To obtain this result, we provide a more general algorithm that solves what we call the incremental, thresholded p-norm flow problem that asks to determine the first edge-insertion in an undirected graph that causes the minimum ℓp-norm flow to decrease below a given threshold in value. Since we solve this thresholded problem, our data structure succeeds against an adaptive adversary that can only see the data structure's output. Furthermore, since our algorithm holds for p = 2, we obtain improved algorithms for dynamically maintaining the effective resistance between a pair of vertices in an undirected graph undergoing edge insertions. Our algorithm builds upon previous dynamic algorithms for approximately solving the minimum-ratio cycle problem that underlie previous advances on the maximum flow problem [Chen-Kyng-Liu-Peng-Probst Gutenberg-Sachdeva, FOCS '22] as well as recent dynamic maximum flow algorithms [v.d.Brand-Liu-Sidford, STOC '23]. Instead of using interior point methods, which were a key component of these recent advances, our algorithm uses an optimization method based on ℓp-norm iterative refinement and the multiplicative weight update method. This ensures a monotonicity property in the minimum-ratio cycle subproblems that allows us to apply known data structures and bypass issues arising from adaptive queries.