Document Open Access Logo

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

Authors Gramoz Goranci, Monika Henzinger, Mikkel Thorup

PDF
Thumbnail PDF

File

LIPIcs.ESA.2016.46.pdf
  • Filesize: 0.52 MB
  • 17 pages

Document Identifiers

Author Details

Gramoz Goranci
Monika Henzinger
Mikkel Thorup

Cite As Get BibTex

Gramoz Goranci, Monika Henzinger, and Mikkel Thorup. Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 46:1-46:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.ESA.2016.46

Abstract

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/epsilon^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+epsilon)-approximation to the minimum cut. The algorithm has ~O(1) amortized update-time and constant query-time.

Subject Classification

Keywords
  • Dynamic Graph Algorithms
  • Minimum Cut
  • Edge Connectivity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud and Virginia Vassilevska Williams. Popular conjectures imply strong lower bounds for dynamic problems. In Proc. of the 55th FOCS, pages 434-443. IEEE, 2014. Google Scholar
  2. Kook Jin Ahn and Sudipto Guha. Graph sparsification in the semi-streaming model. In Proc. of the 36th ICALP, pages 328-338, 2009. Google Scholar
  3. Kook Jin Ahn, Sudipto Guha, and Andrew McGregor. Graph sketches: sparsification, spanners, and subgraphs. In Proc. of the 32nd PODS, pages 5-14, 2012. Google Scholar
  4. András A. Benczúr and David R. Karger. Randomized approximation schemes for cuts and flows in capacitated graphs. SIAM J. Comput., 44(2):290-319, 2015. Google Scholar
  5. Sayan Bhattacharya, Monika Henzinger, Danupon Nanongkai, and Charalampos E. Tsourakakis. Space- and time-efficient algorithm for maintaining dense subgraphs on one-pass dynamic streams. In Proc. of the 47th STOC, pages 173-182, 2015. Google Scholar
  6. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms (3. ed.). MIT Press, 2009. Google Scholar
  7. E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov. On the structure of a family of minimum weighted cuts in a graph. Studies in Discrete Optimization, pages 290-306, 1976. Google Scholar
  8. Yefim Dinitz and Jeffery Westbrook. Maintaining the classes of 4-edge-connectivity in a graph on-line. Algorithmica, 20(3):242-276, 1998. Google Scholar
  9. Harold N. Gabow. Applications of a poset representation to edge connectivity and graph rigidity. In Proc. of the 32nd FOCS, pages 812-821, 1991. Google Scholar
  10. Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci., 50(2):259-273, 1995. Google Scholar
  11. Zvi Galil and Giuseppe F. Italiano. Maintaining the 3-edge-connected components of a graph on-line. SIAM J. Comput., 22(1):11-28, 1993. Google Scholar
  12. David Gibb, Bruce M. Kapron, Valerie King, and Nolan Thorn. Dynamic graph connectivity with improved worst case update time and sublinear space. CoRR, abs/1509.06464, 2015. Google Scholar
  13. Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture. In Proc. of the 47th STOC, pages 21-30, 2015. Google Scholar
  14. Monika Rauch Henzinger. A static 2-approximation algorithm for vertex connectivity and incremental approximation algorithms for edge and vertex connectivity. Journal of Algorithms, 24(1):194-220, 1997. Google Scholar
  15. David Karger. Random Sampling in Graph Optimization Problems. PhD thesis, Stanford University, Stanford, 1994. Google Scholar
  16. David R. Karger. Using randomized sparsification to approximate minimum cuts. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, Arlington, Virginia., pages 424-432, 1994. Google Scholar
  17. David R. Karger. Random sampling in cut, flow, and network design problems. Math. Oper. Res., 24(2):383-413, 1999. Google Scholar
  18. David R. Karger. Minimum cuts in near-linear time. J. ACM, 47(1):46-76, 2000. Google Scholar
  19. Ken-ichi Kawarabayashi and Mikkel Thorup. Deterministic global minimum cut of a simple graph in near-linear time. In Proc. of the 47th STOC, pages 665-674, 2015. Google Scholar
  20. Jonathan A. Kelner and Alex Levin. Spectral sparsification in the semi-streaming setting. Theory Comput. Syst., 53(2):243-262, 2013. Google Scholar
  21. Jakub Lacki and Piotr Sankowski. Min-cuts and shortest cycles in planar graphs in O(n log log n) time. In Proc. of the 19th ESA, pages 155-166, 2011. Google Scholar
  22. Karl Menger. Zur allgemeinen kurventheorie. Fundamenta Mathematicae, 1(10):96-115, 1927. Google Scholar
  23. Hiroshi Nagamochi and Toshihide Ibaraki. A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7(5&6):583-596, 1992. Google Scholar
  24. Danupon Nanongkai and Thatchaphol Saranurak. Dynamic cut oracle. under submission, 2016. Google Scholar
  25. Johannes A. La Poutré. Maintenance of 2- and 3-edge-connected components of graphs II. SIAM J. Comput., 29(5):1521-1549, 2000. Google Scholar
  26. Daniel Dominic Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci., 26(3):362-391, 1983. Google Scholar
  27. Mikkel Thorup. Fully-dynamic min-cut. Combinatorica, 27(1):91-127, 2007. Google Scholar
  28. Mikkel Thorup and David R Karger. Dynamic graph algorithms with applications. In Algorithm Theory-SWAT 2000, pages 1-9. Springer, 2000. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact