Incremental exact min-cut in poly-logarithmic amortized update time

TY - GEN

T1 - Incremental exact min-cut in poly-logarithmic amortized update time

AU - Goranci, Gramoz

AU - Henzinger, Monika

AU - Thorup, Mikkel

N1 - Conference code: 24

PY - 2016/8/1

Y1 - 2016/8/1

N2 - We present a deterministic incremental algorithm for exactly maintaining the size of a minimum cut with 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. of Algorithm 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 Õ(1) amortized update-time and constant query-time.

AB - We present a deterministic incremental algorithm for exactly maintaining the size of a minimum cut with 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. of Algorithm 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 Õ(1) amortized update-time and constant query-time.

U2 - 10.4230/LIPIcs.ESA.2016.46

DO - 10.4230/LIPIcs.ESA.2016.46

M3 - Article in proceedings

SN - 978-3-95977-015-6

T3 - Leibniz International Proceedings in Informatics

BT - 24th Annual European Symposium on Algorithms (ESA 2016)

A2 - Sankowski, Piotr

A2 - Zaroliagis, Christos

PB - Schloss Dagstuhl - Leibniz-Zentrum für Informatik

T2 - 24th Annual European Symposium on Algorithms

Y2 - 22 August 2016 through 26 August 2016

ER -