# Incremental Approximate Maximum Flow via Residual Graph Sparsification

Preprint · Gramoz Goranci, Monika Henzinger, Harald Räcke, A. R. Sricharan

- Archive id: arxiv:2502.09105
- Published: 2025-02-13
- arXiv: https://arxiv.org/abs/2502.09105
- Source URL: https://arxiv.org/abs/2502.09105
- PDF: https://arxiv.org/pdf/2502.09105
- Provenance: arxiv

## Abstract

We give an algorithm that, with high probability, maintains a $(1-ε)$-approximate $s$-$t$ maximum flow in undirected, uncapacitated $n$-vertex graphs undergoing $m$ edge insertions in $\\tilde{O}(m+ n F^\*/ε)$ 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 = Ω(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.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.