Deterministic and Exact Fully-dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time
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^{\Theta(\log^{3/4-c} n)}\) for any \(c \gt 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+\epsilon)\)-approximate fully-dynamic minimum cut algorithm on weighted graphs, for any \(\epsilon \ge 2^{-\Theta(\log^{3/4-c} n)}\), in \(n^{o(1)}\) randomized update time.
Fields of Study & Subjects
Complexity and Algorithms in Graphs
Advanced Graph Theory Research
Limits and Structures in Graph Theory
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 613–663
- Publication date
- 1 January 2026
- Language
- EN