Document Open Access Logo

A Simple Algorithm for Minimum Cuts in Near-Linear Time

Authors Nalin Bhardwaj, Antonio J. Molina Lovett, Bryce Sandlund

PDF

File

Thumbnail PDF
PDF
LIPIcs.SWAT.2020.12.pdf
  • Filesize: 0.52 MB
  • 18 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
Keywords
  • minimum cut
  • sparsification
  • near-linear time
  • packing

Metrics

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

Abstract

We consider the minimum cut problem in undirected, weighted graphs. We give a simple algorithm to find a minimum cut that 2-respects (cuts two edges of) a spanning tree T of a graph G. This procedure can be used in place of the complicated subroutine given in Karger’s near-linear time minimum cut algorithm [Karger, 2000]. We give a self-contained version of Karger’s algorithm with the new procedure, which is easy to state and relatively simple to implement. It produces a minimum cut on an m-edge, n-vertex graph in O(m log³ n) time with high probability, matching the complexity of Karger’s approach.

Cite As Get BibTex

Nalin Bhardwaj, Antonio J. Molina Lovett, and Bryce Sandlund. A Simple Algorithm for Minimum Cuts in Near-Linear Time. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.SWAT.2020.12

Author Details

Nalin Bhardwaj
  • University of California San Diego, CA, USA
Antonio J. Molina Lovett
  • Department of Computer Science, Princeton University, NJ, USA
Bryce Sandlund
  • Cheriton School of Computer Science, University of Waterloo, Canada

Supplementary Materials

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. David L. Applegate, Robert E. Bixby, Vasek Chvatal, and William J. Cook. The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics). Princeton University Press, Princeton, NJ, USA, 2007. Google Scholar
  3. Rodrigo A. Botafogo. Cluster analysis for hypertext systems. In Proceedings of the 16th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR '93, pages 116-125. ACM, 1993. Google Scholar
  4. Parinya Chalermsook, Jittat Fakcharoenphol, and Danupon Nanongkai. A deterministic near-linear time algorithm for finding minimum cuts in planar graphs. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 828-829, 2004. Google Scholar
  5. Chandra S. Chekuri, Andrew V. Goldberg, David R. Karger, Matthew S. Levine, and Cliff Stein. Experimental study of minimum cut algorithms. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 324-333, 1997. Google Scholar
  6. Mohit Daga, Monika Henzinger, Danupon Nanongkai, and Thatchaphol Saranurak. Distributed edge connectivity in sublinear time. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 343-354, 2019. Google Scholar
  7. Michael L. Fredman and Robert Endre Tarjan. Fibonacci heaps and their uses in improved network optimization algorithms. J. ACM, 34(3):596-615, 1987. Google Scholar
  8. H.N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. Journal of Computer and System Sciences, 50(2):259-273, 1995. Google Scholar
  9. Paweł Gawrychowski, Shay Mozes, and Oren Weimann. Minimum cut in O(m log² n) time. CoRR, abs/1911.01145, 2019. Google Scholar
  10. B. Geissmann and L. Gianinazzi. Cache oblivious minimum cut. In International Conference on Algorithms and Complexity, 2017. Google Scholar
  11. Barbara Geissmann and Lukas Gianinazzi. Parallel minimum cuts in near-linear work and low depth. In Proceedings of the 30th on Symposium on Parallelism in Algorithms and Architectures, pages 1-11, 2018. Google Scholar
  12. Mohsen Ghaffari and Fabian Kuhn. Distributed minimum cut approximation. In International Symposium on Distributed Computing, pages 1-15, 2013. Google Scholar
  13. Mohsen Ghaffari, Krzysztof Nowicki, and Mikkel Thorup. Faster algorithms for edge connectivity via random 2-out contractions. In Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020. Google Scholar
  14. R. E. Gomory and T. C. Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551-570, 1961. Google Scholar
  15. Gramoz Goranci, Monika Henzinger, and Mikkel Thorup. Incremental exact min-cut in polylogarithmic amortized update. ACM Transactions on Algorithms, 14(2), 2018. Google Scholar
  16. J.X. Hao and J.B. Orlin. A faster algorithm for finding the minimum cut in a directed graph. Journal of Algorithms, 17(3):424-446, 1994. Google Scholar
  17. Monika Henzinger, Alexander Noe, Christian Schulz, and Darren Strash. Practical minimum cut algorithms. J. Exp. Algorithmics, 23:1.8:1-1.8:22, 2018. Google Scholar
  18. Monika Henzinger, Satish Rao, and Di Wang. Local flow partitioning for faster edge connectivity. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1919-1938, 2017. Google Scholar
  19. M. Jünger, G. Rinaldi, and S. Thienel. Practical performance of efficient minimum cut algorithms. Algorithmica, 26:172, 2000. Google Scholar
  20. David R. Karger. Global min-cuts in RNC, and other ramifications of a simple min-out algorithm. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '93, pages 21-30, 1993. Google Scholar
  21. David R. Karger. A randomized fully polynomial time approximation scheme for the all terminal network reliability problem. In Proceedings of the Twenty-seventh Annual ACM Symposium on Theory of Computing, pages 11-17, 1995. Google Scholar
  22. David R. Karger. Random sampling in cut, flow, and network design problems. Mathematics of Operations Research, 24(2), 1999. Google Scholar
  23. David R. Karger. Minimum cuts in near-linear time. J. ACM, 47(1):46-76, January 2000. Google Scholar
  24. David R. Karger, Philip N. Klein, and Robert E. Tarjan. A randomized linear-time algorithm to find minimum spanning trees. J. ACM, 42(2):321–328, 1995. Google Scholar
  25. David R. Karger and Clifford Stein. A new approach to the minimum cut problem. J. ACM, 43(4):601-640, 1996. Google Scholar
  26. David Ron Karger. Random Sampling in Graph Optimization Problems. PhD thesis, Stanford University, Stanford, CA, USA, 1995. UMI Order No. GAX95-16851. Google Scholar
  27. Ken-Ichi Kawarabayashi and Mikkel Thorup. Deterministic edge connectivity in near-linear time. J. ACM, 66:4:1-4:50, 2018. Google Scholar
  28. Antonio Molina Lovett and Bryce Sandlund. A simple algorithm for minimum cuts in near-linear time. CoRR, abs/1908.11829, 2019. Google Scholar
  29. David W. Matula. A linear time 2 + ε approximation algorithm for edge connectivity. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 500-504, 1993. Google Scholar
  30. Antonio J. Molina Lovett and Bryce Sandlund. personal communication. Google Scholar
  31. Sagnik Mukhopadhyay and Danupon Nanongkai. Weighted min-cut: Sequential, cut-query and streaming algorithms. In Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (to appear), 2020. Google Scholar
  32. Hiroshi Nagamochi and Toshihide Ibaraki. Computing edge-connectivity in multigraphs and capacitated graphs. SIAM Journal on Discrete Mathematics, 5(1):54-66, 1992. Google Scholar
  33. Hiroshi Nagamochi and Toshihide Ibaraki. A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph. Algorithmica, 7:583-596, 1992. Google Scholar
  34. Danupon Nanongkai and Hsin-Hao Su. Almost-tight distributed minimum cut algorithms. In International Symposium on Distributed Computing, 2014. Google Scholar
  35. C. St.J. A. Nash-Williams. Edge-Disjoint Spanning Trees of Finite Graphs. Journal of the London Mathematical Society, s1-36(1):445-450, 1961. Google Scholar
  36. S. A. Plotkin, D. B. Shmoys, and E. Tardos. Fast approximation algorithms for fractional packing and covering problems. In Proceedings 32nd Annual Symposium of Foundations of Computer Science, pages 495-504, 1991. Google Scholar
  37. Aparna Ramanathan and Charles J. Colbourn. Counting almost minimum cutsets with reliability applications. Mathematical Programming, 39:253-261, 1987. Google Scholar
  38. Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362-391, 1983. Google Scholar
  39. Mechthild Stoer and Frank Wagner. A simple min-cut algorithm. J. ACM, 44(4):585-591, 1997. Google Scholar
  40. Robert E. Tarjan and Renato F. Werneck. Self-adjusting top trees. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 813-822, 2005. Google Scholar
  41. Mikkel Thorup. Fully-dynamic min-cut*. Combinatorica, 27(1):91-127, 2007. Google Scholar
  42. Mikkel Thorup and David R. Karger. Dynamic graph algorithms with applications. In Proceedings of the 7th annual scandanavian symposium and workshops on algorithm theory, 2000. Google Scholar
  43. Neal E. Young. Randomized rounding without solving the linear program. In Proceedings of the 6th Annual Symposium on Discrete Algorithms., 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-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact