Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time
Gramoz Goranci, Monika Rauch Henzinger, Mikkel Thorup · ACM Transactions on Algorithms · 2018
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 minimum 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 /ε 2 ) space Monte Carlo algorithm that can process a stream of edge insertions starting from an empty graph, and with high probability, the algorithm maintains a (1+ε)-approximation to the minimum cut. The algorithm has O ((α ( n ) log 3 n )/ε 2 ) amortized update time and constant query time, where α ( n ) stands for the inverse of Ackermann function.