Document Open Access Logo

Minimum Cut in O(m log² n) Time

Authors Paweł Gawrychowski , Shay Mozes , Oren Weimann

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2020.57.pdf
  • Filesize: 0.58 MB
  • 15 pages

Document Identifiers

Author Details

Paweł Gawrychowski
  • University of Wrocław, Poland
Shay Mozes
  • The Interdisciplinary Center Herzliya, Israel
Oren Weimann
  • University of Haifa, Israel

Funding

  • Mozes, Shay: Supported in part by Israel Science Foundation grant 592/17.
  • Weimann, Oren: Supported in part by Israel Science Foundation grant 592/17.

Acknowledgements

We thank Daniel Anderson and Guy Blelloch for drawing our attention to an inaccuracy in a prior version of Section 3.1.

Cite As Get BibTex

Paweł Gawrychowski, Shay Mozes, and Oren Weimann. Minimum Cut in O(m log² n) Time. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ICALP.2020.57

Abstract

We give a randomized algorithm that finds a minimum cut in an undirected weighted m-edge n-vertex graph G with high probability in O(m  log² n) time. This is the first improvement to Karger’s celebrated O(m log³ n) time algorithm from 1996. Our main technical contribution is a deterministic O(m log n) time algorithm that, given a spanning tree T of G, finds a minimum cut of G that 2-respects (cuts two edges of) T.

Subject Classification

ACM Subject Classification
  • Theory of computation → Design and analysis of algorithms
Keywords
  • Minimum cut
  • Minimum 2-respecting cut

Metrics

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

Related Versions

References

  1. Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Maintaining information in fully dynamic trees with top trees. ACM Trans. Algorithms, 1(2):243-264, 2005. Google Scholar
  2. Gerth Stølting Brodal, Rolf Fagerberg, and Christian N. S. Pedersen. Computing the quartet distance between evolutionary trees in time O(n log² n). In 12th ISAAC, pages 731-742, 2001. Google Scholar
  3. Lester R. Ford and Delbert R. Fulkerson. Flows in network. Princeton Univ. Press, 1962. Google Scholar
  4. Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci., 50(2):259-273, 1995. Announced at STOC 1991. Google Scholar
  5. Harold N. Gabow, Jon Louis Bentley, and Robert Endre Tarjan. Scaling and related techniques for geometry problems. In 16th STOC, pages 135-143, 1984. Google Scholar
  6. Barbara Geissmann and Lukas Gianinazzi. Parallel minimum cuts in near-linear work and low depth. In 30th SPAA, pages 1-11, 2018. Google Scholar
  7. Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup. Faster algorithms for edge connectivity via random 2-out contractions. CoRR, abs/1909.00844, 2019. URL: http://arxiv.org/abs/1909.00844.
  8. Andrew V. Goldberg and Satish Rao. Beyond the flow decomposition barrier. J. ACM, 45(5):783-797, 1998. Google Scholar
  9. Andrew V. Goldberg and Robert Endre Tarjan. A new approach to the maximum-flow problem. J. ACM, 35(4):921-940, 1988. Google Scholar
  10. Ralph E. Gomory and Tien Chung Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551-570, 1961. Google Scholar
  11. Jianxiu Hao and James B. Orlin. A faster algorithm for finding the minimum cut in a directed graph. J. Algorithms, 17(3):424-446, 1994. Google Scholar
  12. David Harel and Robert E. Tarjan. Fast algorithms for finding nearest common ancestors. SIAM J. Comput., 13(2):338-355, 1984. Google Scholar
  13. Monika Henzinger, Satish Rao, and Di Wang. Local flow partitioning for faster edge connectivity. In 28th SODA, pages 1919-1938, 2017. Google Scholar
  14. David R. Karger. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In 4th SODA, pages 21-30, 1993. Google Scholar
  15. David R. Karger. Random Sampling in Graph Optimization Problems. PhD thesis, Stanford University, Stanford, CA 94305, 1994. Google Scholar
  16. David R. Karger. Random sampling in cut, flow, and network design problems. Math. Oper. Res., 24(2):383-413, 1999. Announced at STOC 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. Announced at STOC 1996. Google Scholar
  19. David R. Karger, Philip N. Klein, and Robert Endre Tarjan. A randomized linear-time algorithm to find minimum spanning trees. J. ACM, 42(2):321-328, 1995. Google Scholar
  20. David R. Karger and Clifford Stein. A new approach to the minimum cut problem. J. ACM, 43(4):601-640, 1996. Google Scholar
  21. Ken-ichi Kawarabayashi and Mikkel Thorup. Deterministic edge connectivity in near-linear time. J. ACM, 66(1):4:1-4:50, 2019. Google Scholar
  22. Valerie King, S. Rao, and Robert Endre Tarjan. A faster deterministic maximum flow algorithm. J. Algorithms, 17(3):447-474, 1994. Announced at SODA 1992. Google Scholar
  23. Philip N. Klein and Shay Mozes. Optimization algorithms for planar graphs. http://planarity.org. Book draft. URL: http://planarity.org.
  24. Donald Knuth and Andrew Yao. Algorithms and Complexity: New Directions and Recent Results, chapter The complexity of nonuniform random number generation, pages 357-428. Academic Press, 1976. Google Scholar
  25. Yin Tat Lee and Aaron Sidford. Path finding methods for linear programming: Solving linear programs in Õ(√rank) iterations and faster algorithms for maximum flow. In 55th FOCS, pages 424-433, 2014. Google Scholar
  26. Antonio Molina Lovett and Bryce Sandlund. A simple algorithm for minimum cuts in near-linear time. CoRR, abs/1908.11829, 2019. URL: http://arxiv.org/abs/1908.11829.
  27. Aleksander Madry. Computing maximum flow with augmenting electrical flows. In 57th FOCS, pages 593-602, 2016. Google Scholar
  28. David W. Matula. A linear time 2+ε approximation algorithm for edge connectivity. In 4th SODA, pages 500-504, 1993. Google Scholar
  29. Sagnik Mukhopadhyay and Danupon Nanongkai. Weighted min-cut: Sequential, cut-query and streaming algorithms. In 52nd STOC, 2020. To appear. See also URL: https://arxiv.org/abs/1911.01651.
  30. Hiroshi Nagamochi and Toshihide Ibaraki. Computing edge-connectivity in multigraphs and capacitated graphs. SIAM J. Discrete Math., 5(1):54-66, 1992. Google Scholar
  31. 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
  32. Crispin St. J. A. Nash-Williams. Edge disjoint spanning trees of finite graphs. Journal of the London Mathematical Society, 36:445-450, 1961. Google Scholar
  33. James B. Orlin. Max flows in O(nm) time, or better. In 45th STOC, pages 765-774, 2013. Google Scholar
  34. Serge A. Plotkin, David B. Shmoys, and Éva Tardos. Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res., 20(2):257-301, 1995. URL: https://doi.org/10.1287/moor.20.2.257.
  35. Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. J. Comput. Syst. Sci., 26(3):362-391, 1983. Google Scholar
  36. Mikkel Thorup and David R. Karger. Dynamic graph algorithms with applications. In 7th SWAT, pages 1-9, 2000. Google Scholar
  37. Jean Vuillemin. A unifying look at data structures. Communications of the ACM, 23(4):229-239, 1980. Google Scholar
  38. Neal E. Young. Randomized rounding without solving the linear program. In 6th SODA, pages 170-178, 1995. 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