Journal of the ACM Bibliography

Abstract

This paper presents a new approach to finding the minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimization cut form an extremely small fraction of the graph's edges. Using this idea, we give a randomized, strongly polynomial algorithm that finds the minimum cut in an arbitrarily weighted undirected graph with high probability. The algorithm runs in O(n^2 log^3 n) time, a significant improvement over the previous \tilde{O}(mn) time bounds based on maximum flows. It is simple and intuitive and used no complex data structures. Our algorithm can be parallelized to run in RNC with n^2 processors; this gives the first proof that the minimum cut problem can be solved in RNC. The algorithm does more than find a single minimum cut; it finds all of them.

With minor modifications, our algorithm solves two other problems of interest. Our algorithm finds all cuts with value within a multiplicative factor of a of the minimum cut's in expected \tilde{O}(n^{2a}) time, or in RNC with n^{2a} processors. The problem of finding a minimum multiway cut of a graph into r pieces is solved in expected \tilde{O}(n^{2(r-1)}) time, or in RNC with n^{2(r-1)} processors. The ``trace'' of the algorithm's execution on these two problems forms a new compact data structure for representing all small cuts and all multiway cuts in a graph. This data structure can be efficiently transformed into the more standard cactus representation for minimum cuts.

The abstract is also available as a LaTeX file, a DVI file, or a PostScript file.

Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems; G.2.2 [Discrete Mathematics]: Graph Theory -- graph algorithms, network problems; G.3 [Probability and Statistics] -- probabilistic algorithms (including Monte Carlo); I.1.2 [Algebraic Manipulation]: Algorithms

General Terms: Algorithms

Additional Key Words and Phrases: Graph algorithm, minimum cut, network reliability, parallel computing, randomized algorithm

Selected papers that cite this one

• András Benczúr and David R. Karger. Augmenting undirected edge connectivity in \tilde{O}(n^2) time. In Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 500-509, San Francisco, California, 25-27 January 1998.

• David R. Karger and Ray P. Tai. Implementing a fully polynomial time approximation scheme for all terminal network reliability. In Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 334-343, New Orleans, Louisiana, 5-7 January 1997.

• Stavros G. Kolliopoulos and Clifford Stein. Finding real-valued single-source shortest paths in o(n^3) expected time. Journal of Algorithms, 28(1):125-141, July 1998.

Selected references

• András Benczúr. Augmenting undirected connectivity in RNC and in randomized \tilde{O}(n^3) time. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 658-667, Montréal, Québec, Canada, 23-25 May 1994.

• András A. Benczúr and David R. Karger. Approximating s-t minimum cuts in \tilde{O}(n^2) time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 47-55, Philadelphia, Pennsylvania, 22-24 May 1996.

• Joseph Cheriyan and Torben Hagerup. A randomized maximum-flow algorithm. In 30th Annual Symposium on Foundations of Computer Science, pages 118-123, Research Triangle Park, North Carolina, 30 October-1 November 1989. IEEE.

• Joseph Cheriyan and Torben Hagerup. A randomized maximum-flow algorithm. SIAM Journal on Computing, 24(2):203-226, April 1995.

• Stephen Cook, Cynthia Dwork, and Rüdiger Reischuk. Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM Journal on Computing, 15(1):87-97, February 1986.

• E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis. The complexity of multiway cuts (extended abstract). In Proceedings of the Twenty-Fourth Annual ACM Symposium on the Theory of Computing, pages 241-251, Victoria, British Columbia, Canada, 4-6 May 1992.

• E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis. The complexity of multiterminal cuts. SIAM Journal on Computing, 23(4):864-894, August 1994.

• Jack Edmonds and Richard M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2):248-264, April 1972.

• Harold N. Gabow. Applications of a poset representation to edge connectivity and graph rigidity. In 32nd Annual Symposium on Foundations of Computer Science, pages 812-821, San Juan, Puerto Rico, 1-4 October 1991. IEEE.

• Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. In Proceedings of the Twenty Third Annual ACM Symposium on Theory of Computing, pages 112-122, New Orleans, Louisiana, 6-8 May 1991.

• Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. Journal of Computer and System Sciences, 50(2):259-273, April 1995.

• Andrew V. Goldberg and Robert E. Tarjan. A new approach to the maximum-flow problem. Journal of the ACM, 35(4):921-940, October 1988.

• Leslie M. Goldschlager, Ralph A. Shaw, and John Staples. The maximum flow problem is log space complete for P. Theoretical Computer Science, 21(1):105-111, October 1982. Note.

• Olivier Goldschmidt and Dorit S. Hochbaum. Polynomial algorithm for the k-cut problem. In 29th Annual Symposium on Foundations of Computer Science, pages 444-451, White Plains, New York, 24-26 October 1988. IEEE.

• Jianxiu Hao and James B. Orlin. A faster algorithm for finding the minimum cut in a graph. In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 165-174, Orlando, Florida, 27-29 January 1992.

• Jianxiu Hao and James B. Orlin. A faster algorithm for finding the minimum cut in a directed graph. Journal of Algorithms, 17(3):424-446, November 1994.

• Johan Hastad. Almost optimal lower bounds for small depth circuits. In Proceedings of the Eighteenth Annual ACM Symposium on Theory of Computing, pages 6-20, Berkeley, California, 28-30 May 1986.

• David R. Karger. Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 21-30, Austin, Texas, 25-27 January 1993.

• David R. Karger. Random sampling in cut, flow, and network design problems. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 648-657, Montréal, Québec, Canada, 23-25 May 1994.

• David R. Karger. Using randomized sparsification to approximate minimum cuts. In Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 424-432, Arlington, Virginia, 23-25 January 1994.

• 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 the Theory of Computing, pages 11-17, Las Vegas, Nevada, 29 May-1 June 1995.

• David R. Karger. Minimum cuts in near-linear time. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 56-63, Philadelphia, Pennsylvania, 22-24 May 1996.

• David R. Karger and Rajeev Motwani. Derandomization through approximation: An NC algorithm for minimum cuts. In Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 497-506, Montréal, Québec, Canada, 23-25 May 1994.

• David R. Karger and Clifford Stein. An \tilde{O}(n^2) algorithm for minimum cuts. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 757-765, San Diego, California, 16-18 May 1993.

• Samir Khuller and Baruch Schieber. Efficient parallel algorithms for testing k-connectivity and finding disjoint s-t paths in graphs. SIAM Journal on Computing, 20(2):352-375, April 1991.

• V. King, S. Rao, and R. Tarjan. A faster deterministic maximum flow algorithm. In Proceedings of the Third Annual ACM-SIAM Symposium on Discrete Algorithms, pages 157-164, Orlando, Florida, 27-29 January 1992.

• V. King, S. Rao, and R. Tarjan. A faster deterministic maximum flow algorithm. Journal of Algorithms, 17(3):447-474, November 1994.

• Philip Klein, Serge Plotkin, Clifford Stein, and Éva Tardos. Faster approximation algorithms for the unit capacity concurrent flow problem with applications to routing and finding sparse cuts. SIAM Journal on Computing, 23(3):466-487, June 1994.

• Philip Klein, Clifford Stein, and Éva Tardos. Leighton-Rao might be practical: Faster approximation algorithms for concurrent flow with uniform capacities. In Proceedings of the Twenty Second Annual ACM Symposium on Theory of Computing, pages 310-321, Baltimore, Maryland, 14-16 May 1990.

• David W. Matula. Determining edge connectivity in O(nm). In 28th Annual Symposium on Foundations of Computer Science, pages 249-251, Los Angeles, California, 12-14 October 1987. IEEE.

• David W. Matula. A linear time 2 + epsilon approximation algorithm for edge connectivity. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 500-504, Austin, Texas, 25-27 January 1993.

• Steven Phillips and Jeffery Westbrook. Online load balancing and network flow. In Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, pages 402-411, San Diego, California, 16-18 May 1993.

• Yossi Shiloach and Uzi Vishkin. An O(log n) parallel connectivity algorithm. Journal of Algorithms, 3(1):57-67, March 1982.

• Daniel D. Sleator and Robert Endre Tarjan. A data structure for dynamic trees. Journal of Computer and System Sciences, 26(3):362-391, June 1983.

Shortcuts: