Incremental Approximate Maximum Flow via Residual Graph Sparsification

Abstract

We give an algorithm that, with high probability, maintains a $(1-\hat{I}\mu )$-approximate $s$-$t$ maximum flow in undirected, uncapacitated $n$-vertex graphs undergoing $m$ edge insertions in $\tilde{O}(m+n{F}^{\ast }/\hat{I}\mu )$ total update time, where $F^{\ast }$ is the maximum flow on the final graph. This is the first algorithm to achieve polylogarithmic amortized update time for dense graphs ($m=\hat{I}\text{c◯}(n^2)$), and more generally, for graphs where $F^{\ast }=\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.

v2: Our main result now holds against output-adaptive adversaries. v1 appeared at ICALP '25, and v2 accepted to TALG