TY - JOUR

T1 - Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time

AU - Goranci, Gramoz

AU - Henzinger, Monika

AU - Thorup, Mikkel

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - Minimum cut

KW - edge connectivity

KW - space-efficient dynamic graph algorithms

U2 - 10.1115/3174803

DO - 10.1115/3174803

M3 - Journal article

VL - 14

JO - ACM Transactions on Algorithms

JF - ACM Transactions on Algorithms

SN - 1549-6325

IS - 2

M1 - 17

ER -