Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time

We present a deterministic incremental algorithm for exactly maintaining the size of a minimum cut with O(log(3) n log log(2) n) amortized time per edge insertion and O(1) query time. This result partially answers an open question posed by Thorup (2007). It also stays in sharp contrast to a polynomial conditional lower bound for the fully dynamic weighted minimtun cut problem. Our algorithm is obtained by combining a sparsification technique of Kawarabayashi and Thorup (2015) or its recent improvement by Henzinger, Rao, and Wang (2017), and an exact incremental algorithm of Henzinger (1997).

We also study space-efficient incremental algorithms for the minimum cut problem. Concretely, we show that there exists an O(n log n/epsilon(2)) space Monte Carlo algorithm that can process a stream of edge insertions starting from an empty graph, and with high probability, the algorithum maintains a (1 + epsilon)-approximation to the minimtun cut. The algorithum has O((alpha(n) log(3) n) / epsilon(2)) amortized update time and constant query time, where alpha(n) stands for the inverse of Ackermann function.