Fully dynamic approximate minimum cut in subpolynomial time per operation
El-Hayek A, Henzinger M, Li J. 2025. Fully dynamic approximate minimum cut in subpolynomial time per operation. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 750–784.
Download (ext.)
Conference Paper
| Published
| English
Author
Corresponding author has ISTA affiliation
Department
Grant
Abstract
Dynamically maintaining the minimum cut in a graph G under edge insertions and deletion is a fundamental problem in dynamic graph algorithms for which no conditional lower bound on the time per operation exists. In an n-node graph the best known (1 + o (1))-approximate algorithm takes update time [14]. If the minimum cut is guaranteed to be (log n )o (1), a deterministic exact algorithm with n o (1) update time exists [8].
We present the first fully dynamic algorithm for (1 + o (1))-approximate minimum cut with n o(1) update time. Our main technical contribution is to show that it suffices to consider small-volume cuts in suitably contracted graphs.
Publishing Year
Date Published
2025-01-07
Proceedings Title
Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms
Publisher
Society for Industrial and Applied Mathematics
Acknowledgement
This project has received funding from the European Research Council (ERC) under the European Union’sHorizon 2020 research and innovation programme (MoDynStruct, No. 101019564) and the Austrian Science Fund(FWF) grant DOI 10.55776/Z422, grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung, 2020–2024.
Page
750-784
Conference
SODA: Symposium on Discrete Algorithms
Conference Location
New Orleans, LA, United States
Conference Date
2025-01-12 – 2025-01-15
IST-REx-ID
Cite this
El-Hayek A, Henzinger M, Li J. Fully dynamic approximate minimum cut in subpolynomial time per operation. In: Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics; 2025:750-784. doi:10.1137/1.9781611978322.22
El-Hayek, A., Henzinger, M., & Li, J. (2025). Fully dynamic approximate minimum cut in subpolynomial time per operation. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 750–784). New Orleans, LA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611978322.22
El-Hayek, Antoine, Monika Henzinger, and Jason Li. “Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation.” In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, 750–84. Society for Industrial and Applied Mathematics, 2025. https://doi.org/10.1137/1.9781611978322.22.
A. El-Hayek, M. Henzinger, and J. Li, “Fully dynamic approximate minimum cut in subpolynomial time per operation,” in Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA, United States, 2025, pp. 750–784.
El-Hayek A, Henzinger M, Li J. 2025. Fully dynamic approximate minimum cut in subpolynomial time per operation. Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 750–784.
El-Hayek, Antoine, et al. “Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation.” Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics, 2025, pp. 750–84, doi:10.1137/1.9781611978322.22.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Export
Marked PublicationsOpen Data ISTA Research Explorer
Sources
arXiv 2412.15069
Google Scholar