Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time

Understand

We present a deterministic incremental algorithm for \textit{exactly} maintaining the size of a minimum cut with $\widetilde{O}(1)$ amortized time per edge insertion and $O(1)$ query time.

• This result partially answers an open question posed by Thorup [Combinatorica 2007].
• It also stays in sharp contrast to a polynomial conditional lower-bound for the fully-dynamic weighted minimum cut problem.
• Our algorithm is obtained by combining a recent sparsification technique of Kawarabayashi and Thorup [STOC 2015] and an exact incremental algorithm of Henzinger [J.