Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time
El-Hayek A, Henzinger M, Li J. 2026. Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time. Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2026, 613β663.
Download (ext.)
Conference Paper
| Published
| English
Scopus indexed
Author
Department
Grant
Abstract
We present an exact fully-dynamic minimum cut algorithm that runs in ππβ‘(1) deterministic update time when the minimum cut size is at most 2Ξβ‘(log3/4βπβ‘π) for any π >0, improving on the previous algorithm of Jin, Sun, and Thorup (SODA 2024) whose minimum cut size limit is (logβ‘π)πβ‘(1). Combined with graph sparsification, we obtain the first (1 +π)-approximate fully-dynamic minimum cut algorithm on weighted graphs, for any π β₯2βΞβ‘(log3/4βπβ‘π), in ππβ‘(1) randomized update time.
Our main technical contribution is a deterministic local minimum cut algorithm, which replaces the randomized LocalKCut procedure from El-Hayek, Henzinger, and Li (SODA 2025).
Publishing Year
Date Published
2026-01-07
Proceedings Title
Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
Publisher
Society for Industrial and Applied Mathematics
Acknowledgement
Funded by the European union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. This project has received funding from the European Research Council (ERC) under the European Unionβs Horizon 2020 research and innovation programme (MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/I5982. For open access purposes, the author has applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission.
Volume
2026
Page
613-663
Conference
SODA: Symposium on Discrete Algorithms
Conference Location
Vancouver, Canada
Conference Date
2026-01-11 – 2026-01-14
ISSN
eISSN
IST-REx-ID
Cite this
El-Hayek A, Henzinger M, Li J. Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time. In: Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms. Vol 2026. Society for Industrial and Applied Mathematics; 2026:613-663. doi:10.1137/1.9781611978971.25
El-Hayek, A., Henzinger, M., & Li, J. (2026). Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time. In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms (Vol. 2026, pp. 613β663). Vancouver, Canada: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611978971.25
El-Hayek, Antoine, Monika Henzinger, and Jason Li. βDeterministic and Exact Fully-Dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time.β In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, 2026:613β63. Society for Industrial and Applied Mathematics, 2026. https://doi.org/10.1137/1.9781611978971.25.
A. El-Hayek, M. Henzinger, and J. Li, βDeterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time,β in Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, Vancouver, Canada, 2026, vol. 2026, pp. 613β663.
El-Hayek A, Henzinger M, Li J. 2026. Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time. Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete Algorithms vol. 2026, 613β663.
El-Hayek, Antoine, et al. βDeterministic and Exact Fully-Dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time.β Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms, vol. 2026, Society for Industrial and Applied Mathematics, 2026, pp. 613β63, doi:10.1137/1.9781611978971.25.
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 2512.13105
Google Scholar