@inproceedings{21720,
  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).},
  author       = {El-Hayek, Antoine and Henzinger, Monika H and Li, Jason},
  booktitle    = {Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms},
  issn         = {1557-9468},
  location     = {Vancouver, Canada},
  pages        = {613--663},
  publisher    = {Society for Industrial and Applied Mathematics},
  title        = {{Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time}},
  doi          = {10.1137/1.9781611978971.25},
  volume       = {2026},
  year         = {2026},
}