Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time

We present an exact fully-dynamic minimum cut algorithm that runs in n o(1) deterministic update time when the minimum cut size is at most 2 Θ(log 3/4-c n) for any c > 0, improving on the previous algorithm of Jin, Sun, and Thorup (SODA 2024) whose minimum cut size limit is (log n) o(1) . Combined with graph sparsification, we obtain the first (1 + ϵ)-approximate fully-dynamic minimum cut algorithm on weighted graphs, for any ϵ ≥ 2 -Θ(log 3/4-c n) , in n o(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).