Incremental Approximate Maximum Flow via Residual Graph Sparsification
Open Access
- 6 July 2026
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 22 (3) , 1-24
Abstract
We give an algorithm that, with high probability, maintains a \((1-\varepsilon)\) -approximate \(s\text{-}t\) maximum flow in undirected, uncapacitated \( n \) -vertex graphs undergoing \( m \) edge insertions in \(\tilde{O}(m+nF^{*}/\varepsilon)\) total update time, where \(F^{*}\) is the maximum flow on the final graph. This is the first algorithm to achieve polylogarithmic amortized update time for dense graphs ( \(m=\Omega(n^{2})\) ), and more generally, for graphs where \(F^{*}=\tilde{O}(m/n)\) . At the heart of our incremental algorithm is the residual graph sparsification technique of Karger and Levine [STOC ’02, SICOMP ’15], originally designed for computing exact maximum flows in the static setting. Our main contributions are (i) showing how to maintain such sparsifiers for approximate maximum flows in the incremental setting and (ii) generalizing the cut sparsification framework of Fung et al. [STOC ’11, SICOMP ’19] from undirected graphs to balanced directed graphs.
Keywords
All Related Versions
Funding Information
- European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (MoDynStruct, No. 101019564)
- Austrian Science Fund (grant , grant , and grant)
This publication has 28 references indexed in Scilit:
- Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality2024
- Maximum Flow and Minimum-Cost Flow in Almost-Linear Time2022
- Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao2022
- Fast Dynamic Cuts, Distances and Effective Resistances via Vertex Sparsifiers2020
- Nearly Maximum Flows in Nearly Linear Time2013
- The Laplacian Paradigm: Emerging Algorithms for Massive GraphsLecture Notes in Computer Science, 2010
- Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut2009
- A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex ConnectivityJournal of Algorithms, 1997
- A linear-time algorithm for finding a sparsek-connected spanning subgraph of ak-connected graphAlgorithmica, 1992
- Amortized efficiency of a path retrieval data structureTheoretical Computer Science, 1986