article published yes Gramoz Goranci author Monika H Henzinger author 540c9bbd-f2de-11ec-812d-d04a5be856300000-0002-5008-6530 Harald Räcke author A. R. Sricharan author MoHe department The design and evaluation of modern fully dynamic data structures project Efficient algorithms project Static and Dynamic Hierarchical Graph Decompositions project Fast Algorithms for a Reactive Network Layer project 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 Õ(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²)), and more generally, for graphs where F^* = Õ(m/n). At the heart of our incremental algorithm is the residual graph sparsification technique of Karger and Levine [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. [SICOMP '19] from undirected graphs to balanced directed graphs. https://research-explorer.ista.ac.at/download/22716/22740/2026_TransactionsAlgorithms_Goranci.pdf application/pdfno ACM2026 eng 1549-6325 1549-6333 2502.0910510.1145/3816252 223 https://research-explorer.ista.ac.at/record/21280 Goranci G, Henzinger M, Räcke H, Sricharan AR. 2026. Incremental approximate maximum flow via residual graph sparsification. ACM Transactions on Algorithms. 22(3), 31. Goranci, G., Henzinger, M., Räcke, H., &#38; Sricharan, A. R. (2026). Incremental approximate maximum flow via residual graph sparsification. <i>ACM Transactions on Algorithms</i>. ACM. <a href="https://doi.org/10.1145/3816252">https://doi.org/10.1145/3816252</a> G. Goranci, M. Henzinger, H. Räcke, and A. R. Sricharan, “Incremental approximate maximum flow via residual graph sparsification,” <i>ACM Transactions on Algorithms</i>, vol. 22, no. 3. ACM, 2026. Goranci G, Henzinger M, Räcke H, Sricharan AR. Incremental approximate maximum flow via residual graph sparsification. <i>ACM Transactions on Algorithms</i>. 2026;22(3). doi:<a href="https://doi.org/10.1145/3816252">10.1145/3816252</a> G. Goranci, M. Henzinger, H. Räcke, A.R. Sricharan, ACM Transactions on Algorithms 22 (2026). Goranci, Gramoz, et al. “Incremental Approximate Maximum Flow via Residual Graph Sparsification.” <i>ACM Transactions on Algorithms</i>, vol. 22, no. 3, 31, ACM, 2026, doi:<a href="https://doi.org/10.1145/3816252">10.1145/3816252</a>. Goranci, Gramoz, Monika Henzinger, Harald Räcke, and A. R. Sricharan. “Incremental Approximate Maximum Flow via Residual Graph Sparsification.” <i>ACM Transactions on Algorithms</i>. ACM, 2026. <a href="https://doi.org/10.1145/3816252">https://doi.org/10.1145/3816252</a>. 227162026-08-16T22:01:43Z2026-08-20T06:28:01Z