---
OA_place: publisher
OA_type: gold
PlanS_conform: '1'
_id: '22716'
abstract:
- lang: eng
  text: 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.
acknowledgement: "M. Henzinger: This project has received funding from the European
  Research Council (ERC) under the European Union’s\r\nHorizon 2020 research and innovation
  programme (MoDynStruct, No. 101019564)   and the Austrian Science Fund\r\n(FWF)
  grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775
  with additional funding from the\r\nnetidee SCIENCE Stiftung, 2020–2024. Views and
  opinions expressed are those of the author(s) only and do not necessarily\r\nreflect
  those of the European Union or the European Research Council Executive Agency. Neither
  the European Union nor\r\nthe granting authority can be held responsible for them"
article_number: '31'
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Gramoz
  full_name: Goranci, Gramoz
  last_name: Goranci
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Harald
  full_name: Räcke, Harald
  last_name: Räcke
- first_name: A. R.
  full_name: Sricharan, A. R.
  last_name: Sricharan
citation:
  ama: 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>
  apa: 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>
  chicago: 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>.
  ieee: 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.
  ista: 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.
  mla: 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>.
  short: G. Goranci, M. Henzinger, H. Räcke, A.R. Sricharan, ACM Transactions on Algorithms
    22 (2026).
corr_author: '1'
das_tickbox: '0'
date_created: 2026-08-16T22:01:43Z
date_published: 2026-07-06T00:00:00Z
date_updated: 2026-08-20T06:28:01Z
day: '06'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.1145/3816252
ec_funded: 1
external_id:
  arxiv:
  - '2502.09105'
file:
- access_level: open_access
  checksum: 97969d26dab25c3a35be3ae4dd0fd9ee
  content_type: application/pdf
  creator: dernst
  date_created: 2026-08-20T06:19:51Z
  date_updated: 2026-08-20T06:19:51Z
  file_id: '22740'
  file_name: 2026_TransactionsAlgorithms_Goranci.pdf
  file_size: 2272512
  relation: main_file
  success: 1
file_date_updated: 2026-08-20T06:19:51Z
has_accepted_license: '1'
intvolume: '        22'
issue: '3'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
  call_identifier: H2020
  grant_number: '101019564'
  name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
  grant_number: Z00422
  name: Efficient algorithms
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
  grant_number: I05982
  name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
  grant_number: P33775
  name: Fast Algorithms for a Reactive Network Layer
publication: ACM Transactions on Algorithms
publication_identifier:
  eissn:
  - 1549-6333
  issn:
  - 1549-6325
publication_status: published
publisher: ACM
quality_controlled: '1'
related_material:
  record:
  - id: '21280'
    relation: earlier_version
    status: public
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: yes
title: Incremental approximate maximum flow via residual graph sparsification
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 22
year: '2026'
...