Minimum cuts in near-linear time

ABSTRACT

We significantly improve known time bounds for solving the minimum cut problem on undirected graphs. We use a "semiduality" between minimum cuts and maximum spanning tree packings combined with our previously developed random sampling techniques. We give a randomized (Monte Carlo) algorithm that finds a minimum cut in an m-edge, n-vertex graph with high probability in O(m log3 n) time. We also give a simpler randomized algorithm that finds all minimum cuts with high probability in O(m log3 n) time. This variant has an optimal RNC parallelization. Both variants improve on the previous best time bound of O(n2 log3 n). Other applications of the tree-packing approach are new, nearly tight bounds on the number of near-minimum cuts a graph may have and a new data structure for representing them in a space-efficient manner.

REFERENCES

• 1: Francisco Barahona, Packing spanning trees, Mathematics of Operations Research, v.20 n.1, p.104-115, Feb. 1995 [doi>10.1287/moor.20.1.104]
• 2: A. A. Benczur, A representation of cuts within 6/5 times the edge connectivity with applications, Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS'95), p.92, October 23-25, 1995
• 3: Omer Berkman , Uzi Vishkin, Recursive star-tree parallel data structure, SIAM Journal on Computing, v.22 n.2, p.221-242, April 1993 [doi>10.1137/0222017]
• 4: BOLLOBAS, B. 1985. Random Graphs. Harcourt Brace Janovich, San Diego, Calif.
• 5: Rodrigo A. Botafogo, Cluster analysis for hypertext systems, Proceedings of the 16th annual international ACM SIGIR conference on Research and development in information retrieval, p.116-125, June 27-July 01, 1993, Pittsburgh, Pennsylvania, United States [doi>10.1145/160688.160704]
• 6: DANTZIG, G. B., FULKERSON, D. R., AND JOHNSON, S.M. 1954. Solution of a large-scale traveling salesman problem. Oper. Re. 2, 393-410.
• 7: DINITZ, E. A., KARZANOV, A. V., AND LOMONOSOV, M.V. 1976. On the structure of a family of minimum weighted cuts in a graph. In Studies in Discrete Optimization, A. A. Fridman, ed. Nauka Publishers, pp. 290-306.
• 8: EDMONDS, J. 1972. Edge-disjoint branchings. In Combinatorial Algorithms, R. Rustin, ed. Algorithmics Press, pp. 91-96. FORD, L. R., JR., AND FULKERSON, D. R. 1962. Flows in Networks. Princeton University Press, Princeton, N. J.
• 9: Harold N. Gabow, A matroid approach to finding edge connectivity and packing arborescences, Journal of Computer and System Sciences, v.50 n.2, p.259-273, April 1995
• 10: GABOW, H. N., AND TARJAN, R.E. 1985. A linear time algorithm for a special case of disjoint set union. J. Comput. Syst. Sci. 30, 209-221.
• 11: GABOW, H. N., AND WESTERMANN, H. H. 1992. Forests, frames, and games: Algorithms for matroid sums and applications. Algorithmica 7, 5, 465-497.
• 12: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 13: Andrew V. Goldberg , Robert E. Tarjan, A new approach to the maximum-flow problem, Journal of the ACM (JACM), v.35 n.4, p.921-940, Oct. 1988 [doi>10.1145/48014.61051]
• 14: GOMORY, R. E., AND HU, T.C. 1961. Multi-terminal network flows. J. Soc. Indust. Appl. Math. 9, 4 (Dec.), 551-570.
• 15: Jianxiu Hao , James B. Orlin, A faster algorithm for finding the minimum cut in a directed graph, Journal of Algorithms, v.17 n.3, p.424-446, Nov. 1994
• 16: Monika R. Henzinger , Valerie King, Randomized fully dynamic graph algorithms with polylogarithmic time per operation, Journal of the ACM (JACM), v.46 n.4, p.502-516, July 1999 [doi>10.1145/320211.320215]
• 17: Monika Henzinger , David P. Williamson, On the number of small cuts in a graph, Information Processing Letters, v.59 n.1, p.41-44, July 8, 1996 [doi>10.1016/0020-0190(96)00079-8]
• 18: Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.79-89, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276715]
• 19: Donald B. Johnson , Panagiotis Metaxas, A parallel algorithm for computing minimum spanning trees, Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures, p.363-372, June 29-July 01, 1992, San Diego, California, United States [doi>10.1145/140901.141917]
• 20: David R. Karger, Global min-cuts in RNC, and other ramifications of a simple min-out algorithm, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.21-30, January 25-27, 1993, Austin, Texas, United States
• 21: David Ron Karger, Random sampling in graph optimization problems, Stanford University, Stanford, CA, 1995
• 22: KARGER, D.R. 1998. Random sampling and greedy sparsification in matroid optimization problems. Math. Prog. B 82, 1-2 (June), 41-81.
• 23: A. A. Tsay , W. S. Lovejoy , David R. Karger, Random Sampling in Cut, Flow, and Network Design Problems, Mathematics of Operations Research, v.24 n.2, p.383-413, February 1999 [doi>10.1287/moor.24.2.383]
• 24: David R. Karger, A Randomized Fully Polynomial Time Approximation Scheme for the All-Terminal Network Reliability Problem, SIAM Journal on Computing, v.29 n.2, p.492-514, Oct. 1999 [doi>10.1137/S0097539796298340]
• 25: David R. Karger , Clifford Stein, A new approach to the minimum cut problem, Journal of the ACM (JACM), v.43 n.4, p.601-640, July 1996 [doi>10.1145/234533.234534]
• 26: Richard M. Karp , Vijaya Ramachandran, Parallel algorithms for shared-memory machines, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
• 27: LAWLER, E. L., LENSTRA, J. K., RINOOY NAN, A. H. G., AND SHMOYS, D. B., EDS. 1985. The Traveling Salesman Problem. Wiley, New York.
• 28: Rajeev Motwani , Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, New York, NY, 1995
• 29: Hiroshi Nagamochi , Toshihide Ibaraki, Computing edge-connectivity in multigraphs and capacitated graphs, SIAM Journal on Discrete Mathematics, v.5 n.1, p.54-66, Feb. 1992 [doi>10.1137/0405004]
• 30: NAGAMOCHI, H., AND IBARAKI, T. 1992b. Linear time algorithms for finding k-edge connected and k-node connected spanning subgraphs. Algorithmica 7, 583-596.
• 31: NAGAMOCHI, H., NISHIMURA, K., AND IBARAKI, T. 1994. Computing all small cuts in an undirected network. Tech. Rep. 94007. Kyoto Univ. Kyoto, Japan.
• 32: NASH-WILLIAMS, C. ST. J.A. 1961. Edge disjoint spanning trees of finite graphs. J. London Math. Soc. 36, 445-450.
• 33: M. Padberg , G. Rinaldi, An efficient algorithm for the minimum capacity cut problem, Mathematical Programming: Series A and B, v.47 n.1, p.19-36, May 1990 [doi>10.1007/BF01580850]
• 34: PICARD, J.-C., AND QUEYRANNE, M. 1982. Selected applications of minimum cuts in networks. LN.F.O.R: Canad. J. Oper. Res. Inf. Proc. 20, (Nov.), 394-422.
• 35: Serge A. Plotkin , David B. Shmoys , Éva Tardos, Fast approximation algorithms for fractional packing and covering problems, Proceedings of the 32nd annual symposium on Foundations of computer science, p.495-504, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185411]
• 36: Baruch Schieber , Uzi Vishkin, On finding lowest common ancestors: simplification and parallelization, SIAM Journal on Computing, v.17 n.6, p.1253-1262, Dec. 1988 [doi>10.1137/0217079]
• 37: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]
• 38: Vijay V. Vazirani , Mihalis Yannakakis, Suboptimal Cuts: Their Enumeration, Weight and Number (Extended Abstract), Proceedings of the 19th International Colloquium on Automata, Languages and Programming, p.366-377, July 13-17, 1992

INDEX TERMS

Primary Classification:
  E. Data

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory

Keywords:
Monte Carlo algorithm, connectivity, min-cut, optimization, tree packing