Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time El-Hayek, Antoine ; https://orcid.org/0000-0003-4268-7368 Henzinger, Monika H ; https://orcid.org/0000-0002-5008-6530 Li, Jason 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). Society for Industrial and Applied Mathematics 2026 info:eu-repo/semantics/conferenceObject doc-type:conferenceObject text http://purl.org/coar/resource_type/c_5794 https://research-explorer.ista.ac.at/record/21720 El-Hayek A, Henzinger M, Li J. Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time. In: <i>Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms</i>. Vol 2026. Society for Industrial and Applied Mathematics; 2026:613-663. doi:<a href="https://doi.org/10.1137/1.9781611978971.25">10.1137/1.9781611978971.25</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1137/1.9781611978971.25 info:eu-repo/semantics/altIdentifier/issn/1071-9040 info:eu-repo/semantics/altIdentifier/e-issn/1557-9468 info:eu-repo/semantics/altIdentifier/e-isbn/9781611978971 info:eu-repo/semantics/altIdentifier/arxiv/2512.13105 info:eu-repo/semantics/openAccess