DROPS

Document

Track A: Algorithms, Complexity and Games

DOI: 10.4230/LIPIcs.ICALP.2026.133

Partially-Dynamic Maximum Flow in Dense Graphs

Authors: Egor Kravchenko and Maximilian Probst Gutenberg

Published in: LIPIcs, Volume 374, 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)

Abstract

We give the first algorithms that, with high probability, maintain (1-ε)-approximate s-t maximum flow in an n-vertex undirected, capacitated graph undergoing either only edge insertions or only edge deletions in total update time Õ_ε(n²). For dense graphs, this yields polylogarithmic amortized update time, which was previously only obtained for the special case of uncapacitated graphs undergoing edge insertions. We develop the following two algorithms: - For graphs undergoing deletions, we generalize the congestion-balancing framework from [Aaron Bernstein et al., 2020], which was developed for maximum matching. We then show that this framework can be simulated on cut sparsifiers, which yields significant speed-ups. - For graphs undergoing insertions, we show that the sparsification techniques by Eppstein et al. [Eppstein et al., 1997] can be combined more directly with the techniques from Henzinger and Goranci [Goranci and Henzinger, 2023]. We thereby bypass the need to dynamize the more involved residual graph sparsification approach by Levin and Karger [Karger and Levine, 2015] suggested in [Goranci et al., 2025], and extend their result to capacitated graphs.

Cite as

Egor Kravchenko and Maximilian Probst Gutenberg. Partially-Dynamic Maximum Flow in Dense Graphs. In 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 374, pp. 133:1-133:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kravchenko_et_al:LIPIcs.ICALP.2026.133,
  author =	{Kravchenko, Egor and Probst Gutenberg, Maximilian},
  title =	{{Partially-Dynamic Maximum Flow in Dense Graphs}},
  booktitle =	{53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
  pages =	{133:1--133:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-428-4},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{374},
  editor =	{Bhattacharya, Sayan and Nanongkai, Danupon and Benedikt, Michael and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.133},
  URN =		{urn:nbn:de:0030-drops-265226},
  doi =		{10.4230/LIPIcs.ICALP.2026.133},
  annote =	{Keywords: Maximum Flow, Dynamic Graph Algorithm, Data Structure}
}

Search Results

Documents authored by Kravchenko, Egor

Partially-Dynamic Maximum Flow in Dense Graphs

Abstract

Cite as

Thanks for your feedback!

Could not send message