Document Open Access Logo

Efficient Data Structures for Incremental Exact and Approximate Maximum Flow

Authors Gramoz Goranci , Monika Henzinger

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2023.69.pdf
  • Filesize: 0.83 MB
  • 14 pages

Document Identifiers

Author Details

Gramoz Goranci
  • Faculty of Computer Science, Universität Wien, Austria
Monika Henzinger
  • Institute of Science and Technology Austria (ISTA), Klosterneuburg, Austria

Funding

This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101019564 "The Design of Modern Fully Dynamic Data Structures (MoDynStruct)" and from the Austrian Science Fund (FWF) project "Static and Dynamic Hierarchical Graph Decompositions", I 5982-N, and project "Fast Algorithms for a Reactive Network Layer (ReactNet)", P 33775-N, with additional funding from the netidee SCIENCE Stiftung, 2020-2024.

Acknowledgements

This work was done in part while Gramoz Goranci was at Institute for Theoretical Studies, ETH Zurich, Switzerland. There, he was supported by Dr. Max Rössler, the Walter Haefner Foundation and the ETH Zürich Foundation. We also thank Richard Peng, Thatchaphol Saranurak, Sebastian Forster and Sushant Sachdeva for helpful discussions, and the anonymous reviewers for their insightful comments.

Cite AsGet BibTex

Gramoz Goranci and Monika Henzinger. Efficient Data Structures for Incremental Exact and Approximate Maximum Flow. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 69:1-69:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ICALP.2023.69

Abstract

We show an (1+ε)-approximation algorithm for maintaining maximum s-t flow under m edge insertions in m^{1/2+o(1)} ε^{-1/2} amortized update time for directed, unweighted graphs. This constitutes the first sublinear dynamic maximum flow algorithm in general sparse graphs with arbitrarily good approximation guarantee. Furthermore we give an algorithm that maintains an exact maximum s-t flow under m edge insertions in an n-node graph in Õ(n^{5/2}) total update time. For sufficiently dense graphs, this gives to the first exact incremental algorithm with sub-linear amortized update time for maintaining maximum flows.

Subject Classification

ACM Subject Classification
  • Theory of computation → Dynamic graph algorithms
Keywords
  • dynamic graph algorithms
  • maximum flow
  • data structures

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Ittai Abraham, David Durfee, Ioannis Koutis, Sebastian Krinninger, and Richard Peng. On fully dynamic graph sparsifiers. In Symposium on Foundations of Computer Science (FOCS), pages 335-344, 2016. Google Scholar
  2. Yuri Boykov, Olga Veksler, and Ramin Zabih. Fast approximate energy minimization via graph cuts. IEEE Transactions on pattern analysis and machine intelligence, 23(11):1222-1239, 2001. Google Scholar
  3. Li Chen, Gramoz Goranci, Monika Henzinger, Richard Peng, and Thatchaphol Saranurak. Fast dynamic cuts, distances and effective resistances via vertex sparsifiers. In Symposium on Foundations of Computer Science (FOCS), 2020. Google Scholar
  4. Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenberg, and Sushant Sachdeva. Maximum flow and minimum-cost flow in almost-linear time. In Annual Symposium on Foundations of Computer Science (FOCS), pages 612-623, 2022. Google Scholar
  5. Ho Yee Cheung, Tsz Chiu Kwok, and Lap Chi Lau. Fast matrix rank algorithms and applications. J. ACM, 60(5):31:1-31:25, 2013. Google Scholar
  6. Paul Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, and Shang-Hua Teng. Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. In Symposium on Theory of Computing (STOC), pages 273-282, 2011. Google Scholar
  7. Søren Dahlgaard. On the hardness of partially dynamic graph problems and connections to diameter. In International Colloquium on Automata, Languages, and Programming (ICALP), pages 48:1-48:14, 2016. Google Scholar
  8. Gary William Flake, Robert E Tarjan, and Kostas Tsioutsiouliklis. Graph clustering and minimum cut trees. Internet Mathematics, 1(4):385-408, 2004. Google Scholar
  9. L. R. Ford and D. R. Fulkerson. Maximal flow through a network. Canadian Journal of Mathematics, 8:399-404, 1956. Google Scholar
  10. Zvi Galil and Xiangdong Yu. Short length versions of menger’s theorem (extended abstract). In Frank Thomson Leighton and Allan Borodin, editors, Symposium on Theory of Computing (STOC), pages 499-508. ACM, 1995. Google Scholar
  11. R. E. Gomory and T. C. Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551-570, 1961. Google Scholar
  12. Gramoz Goranci, Monika Henzinger, Danupon Nanongkai, Thatchaphol Saranurak, Mikkel Thorup, and Christian Wulff-Nilsen. Fully dynamic exact edge connectivity in sublinear time. In Symposium on Discrete Algorithms (SODA) 2023, pages 70-86, 2023. Google Scholar
  13. Gramoz Goranci, Harald Räcke, Thatchaphol Saranurak, and Zihan Tan. The expander hierarchy and its applications to dynamic graph algorithms. In Symposium on Discrete Algorithms (SODA), 2021. Google Scholar
  14. Manoj Gupta and Shahbaz Khan. Simple dynamic algorithms for maximal independent set, maximum flow and maximum matching. In Symposium on Simplicity in Algorithms (SOSA) 2021, pages 86-91, 2021. Google Scholar
  15. Manoj Gupta and Richard Peng. Fully dynamic (1+ e)-approximate matchings. In Symposium on Foundations of Computer Science (FOCS), pages 548-557, 2013. Google Scholar
  16. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Symposium on Theory of Computing (STOC), pages 21-30, 2015. Google Scholar
  17. Monika Rauch Henzinger. A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity. J. Algorithms, 24(1):194-220, 1997. Google Scholar
  18. Jacob Holm, Kristian de Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. J. ACM, 48(4):723-760, 2001. Google Scholar
  19. Giuseppe F. Italiano. Amortized efficiency of a path retrieval data structure. Theor. Comput. Sci., 48(3):273-281, 1986. Google Scholar
  20. Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, and Christian Wulff-Nilsen. Improved algorithms for min cut and max flow in undirected planar graphs. In Symposium on Theory of Computing (STOC), pages 313-322, 2011. Google Scholar
  21. Adam Karczmarz. Fully dynamic algorithms for minimum weight cycle and related problems. In Nikhil Bansal, Emanuela Merelli, and James Worrell, editors, International Colloquium on Automata, Languages, and Programming (ICALP), volume 198 of LIPIcs, pages 83:1-83:20, 2021. Google Scholar
  22. David R. Karger and Matthew S. Levine. Finding maximum flows in undirected graphs seems easier than bipartite matching. In Symposium on the Theory of Computing (STOC), pages 69-78. ACM, 1998. Google Scholar
  23. Jonathan A. Kelner, Yin Tat Lee, Lorenzo Orecchia, and Aaron Sidford. An almost-linear-time algorithm for approximate max flow in undirected graphs, and its multicommodity generalizations. In Symposium on Discrete Algorithms (SODA), pages 217-226, 2014. Google Scholar
  24. Rohit Khandekar, Satish Rao, and Umesh V. Vazirani. Graph partitioning using single commodity flows. J. ACM, 56(4):19:1-19:15, 2009. Google Scholar
  25. Yang P. Liu and Aaron Sidford. Faster divergence maximization for faster maximum flow. In Symposium on Foundations of Computer Science (FOCS), 2020. Google Scholar
  26. Aleksander Madry. Navigating central path with electrical flows: From flows to matchings, and back. In Symposium on Foundations of Computer Science (FOCS), pages 253-262, 2013. Google Scholar
  27. Aleksander Madry. Computing maximum flow with augmenting electrical flows. In Symposium on Foundations of Computer Science (FOCS), pages 593-602, 2016. Google Scholar
  28. Richard Peng. Approximate undirected maximum flows in O(mpolylog(n)) time. In Symposium on Discrete Algorithms (SODA), pages 1862-1867, 2016. Google Scholar
  29. Thatchaphol Saranurak and Di Wang. Expander decomposition and pruning: Faster, stronger, and simpler. In Timothy M. Chan, editor, Symposium on Discrete Algorithms (SODA), pages 2616-2635. SIAM, 2019. Google Scholar
  30. Jonah Sherman. Nearly maximum flows in nearly linear time. In Symposium on Foundations of Computer Science (FOCS), pages 263-269, 2013. Google Scholar
  31. Jonah Sherman. Area-convexity, l_∞-regularization, and undirected multicommodity flow. In Symposium on Theory of Computing (STOC), pages 452-460, 2017. Google Scholar
  32. Jan van den Brand, Yang P. Liu, and Aaron Sidford. Dynamic maxflow via dynamic interior point methods. CoRR, abs/2212.06315, 2022. to appear at STOC'23. URL: https://arxiv.org/abs/2212.06315.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact