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

2025/12/15 by Antoine El-Hayek, Monika Henzinger, El-Hayek, Antoine +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2512.13105

openalex publication_date 2025/12/15 · openalex created_date 2025/12/17 · openalex updated_date 2026/07/28

Abstract

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-cn) 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-cn), 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).

Related

• Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time
• Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation
• Practical Fully Dynamic Minimum Cut Algorithms
• Fast and Deterministic Approximations for k-Cut
• Minimum Cut in O(mlog² n) Time