Fully Dynamic Approximate Minimum Cut in Subpolynomial Time per Operation

Dynamically maintaining the minimum cut in a graph G under edge insertions and deletions is a fundamental problem in dynamic graph algorithms for which no conditional lower bound on the time per operation exists. In an n-node graph the best known (1 + o(1))-approximate algorithm takes Õ( √ n) update time [14]. If the minimum cut is guaranteed to be (log n) o(1) , a deterministic exact algorithm with n o(1) update time exists [8].

We present the first fully dynamic algorithm for (1 + o(1))-approximate minimum cut with n o(1) update time. Our main technical contribution is to show that it suffices to consider small-volume cuts in suitably contracted graphs.