Fully Dynamic Min-Cut of Superconstant Size in Subpolynomial Time

We present a deterministic fully dynamic algorithm with subpolynomial worst-case time per graph update such that after processing each update of the graph, the algorithm outputs a minimum cut of the graph if the graph has a cut of size at most c for some c = (log n) o(1) . Previously, the best update time was O( √ n) for any c > 2 and c = O(log n) [Thorup, Combinatorica'07].