A new approach to the minimum cut problem

ABSTRACT

This paper present a new approach to finding minimum cuts in undirected graphs. The fundamental principle is simple: the edges in a graph's minimum 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(n2log3n) time, a significant improvement over the previous O˜(mn) time bounds based on maximum flows. It is simple and intuitive and uses no complex data structures. Our algorithm can be parallelized to run in RNC with n2 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 &agr; of the minimum cut's in expected O˜(n2&agr;) time, or in RNC with n2&agr; processors. The problem of finding a minimum multiway cut of graph into r pieces is solved in expected O˜(n2(r-1)) time, or in RNC with n2(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 representing for minimum cuts.

REFERENCES

• 1: D. Applegate , R. Bixby , V. Chvatal , B. Cook, Finding Cuts in the TSP (A preliminary report), Certer for Discrete Mathematics & Theoretical Computer Science, 1995
• 2: András A. Benczúr, Augmenting undirected connectivity in RNC and in randomized Õ(n³) time, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.658-667, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195425]
• 3: András A. Benczúr , David R. Karger, Approximating s-t minimum cuts in Õ(n²) time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.47-55, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237827]
• 4: ~BOLLOBAS, B. 1986. Extremal graph theory with emphasis on probabilistic methods. Number 62 in ~ Regional Conference Series in Mathematics. American Mathematical Society, Providence, R.I.
• 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: Siddhartha Chatterjee , Robert Schreiber , Thomas J. Sheffler , John R. Gilbert, Array Distribution in Data-Parallel Programs, Proceedings of the 7th International Workshop on Languages and Compilers for Parallel Computing, p.76-91, August 08-10, 1994
• 7: Joseph Cheriyan , Torben Hagerup, A Randomized Maximum-Flow Algorithm, SIAM Journal on Computing, v.24 n.2, p.203-226, April 1995 [doi>10.1137/S0097539791221529]
• 8: ~CHERNOFF, H. 1952. A measure of the asymptotic efficiency for tests of a hypothesis based on the ~ sum of observations. Ann. Math. Stat. 23, 493-509.
• 9: Charles J. Colbourn, The Combinatorics of Network Reliability, Oxford University Press, Inc., New York, NY, 1987
• 10: Stephen Cook , Cynthia Dwork , Ru&duml;ger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM Journal on Computing, v.15 n.1, p.87-97, Feb. 1986 [doi>10.1137/0215006]
• 11: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 12: E. Dahlhaus , D. S. Johnson , C. H. Papadimitriou , P. D. Seymour , M. Yannakakis, The Complexity of Multiterminal Cuts, SIAM Journal on Computing, v.23 n.4, p.864-894, Aug. 1994 [doi>10.1137/S0097539792225297]
• 13: ~DANTZIG, G. B., FULKERSON, D. R., AND JOHNSON, S.M. 1954. Solution of a large-scale traveling ~ salesman problem. Op. Res. 2, 393-410.
• 14: 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.
• 15: Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
• 16: ELIAS, P., FEINSTEIN, h., AND SHANNON, C.E. 1956. Note on maximum flow through a network. ~ IRE Trans. Inf. Theory IT-2, 117-199.
• 17: FORD, JR., L. R., AND FULKERSON, D.R. 1956. Maximal flow through a network. Can. J. Math. 8, ~ 399-404, 1956.
• 18: ~FORD, JR., L. R., AND FULKERSON, D. R. 1962. Flows in Networks. Princeton University Press, ~ Princeton, N.J.
• 19: FRANK, A. 1994. On the edge-connectivity algorithm of Nagamochi and Ibaraki. Labarotoire ~ Artemis, IMAG, Universit6 J. Fourier, Grenoble, Switzerland.
• 20: Harold N. Gabow, Applications of a poset representation to edge connectivity and graph rigidity, Proceedings of the 32nd annual symposium on Foundations of computer science, p.812-821, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185453]
• 21: 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
• 22: GALIL, Z., AND PAN, V. 1988. Improved processor bounds for combinatorial problems in ~X~. ~ Combinatorica 8, 189-200.
• 23: 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
• 24: 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]
• 25: GOLDSCHLAGER, L. M., SHAW, R. A., AND STAPLES, J. 1982. The maximum flow problem is ~ logspace complete for P. Theoret. Comput. Sci. 21, 105-111.
• 26: GOLDSCHMIDT, O., AND HOCHBAUM, D. 1988. Polynomial algorithm for the k-cut problem. In ~ Proceedings of the 29th Annual Symposium on the Foundations of Computer Science. IEEE ~ Computer Society Press, pp. 444-451.
• 27: GOMOR~, R. U., AND HU, T.C. 1961. Multi-terminal network flows. J. Soc. Indust. Appl. Math. 9, 4 ~ (Dec.), 551-570.
• 28: Shay Halperin , Uri Zwick, An optimal randomized logarithmic time connectivity algorithm for the EREW PRAM (extended abstract), Proceedings of the sixth annual ACM symposium on Parallel algorithms and architectures, p.1-10, June 27-29, 1994, Cape May, New Jersey, United States [doi>10.1145/181014.181017]
• 29: 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
• 30: HASTAD, J. 1989. Almost optimal lower bounds for small depth circuits. Adv. Comput. Res. 5, ~ 143-170.
• 31: 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
• 32: David R. Karger, Random sampling in cut, flow, and network design problems, Proceedings of the twenty-sixth annual ACM symposium on Theory of computing, p.648-657, May 23-25, 1994, Montreal, Quebec, Canada [doi>10.1145/195058.195422]
• 33: David Ron Karger, Random sampling in graph optimization problems, Stanford University, Stanford, CA, 1995
• 34: David R. Karger, Using randomized sparsification to approximate minimum cuts, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.424-432, January 23-25, 1994, Arlington, Virginia, United States
• 35: David R. Karger, A randomized fully polynomial time approximation scheme for the all terminal network reliability problem, Proceedings of the twenty-seventh annual ACM symposium on Theory of computing, p.11-17, May 29-June 01, 1995, Las Vegas, Nevada, United States [doi>10.1145/225058.225069]
• 36: David R. Karger, Minimum cuts in near-linear time, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.56-63, May 22-24, 1996, Philadelphia, Pennsylvania, United States [doi>10.1145/237814.237829]
• 37: David R. Karger , Rajeev Motwani, An $\NC$ Algorithm for Minimum Cuts, SIAM Journal on Computing, v.26 n.1, p.255-272, Feb. 1997 [doi>10.1137/S0097539794273083]
• 38: David R. Karger , Clifford Stein, An Õ(n²) algorithm for minimum cuts, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.757-765, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167281]
• 39: 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
• 40: R M Karp , E Upfal , A Wigderson, Constructing a perfect matching is in random NC, Combinatorica, v.6 n.1, p.35-48, 1986 [doi>10.1007/BF02579407]
• 41: KARZANOV, A. V., AND TIMOFEEV, U.A. 1986. Efficient algorithm for finding all minimal edge ~ cuts of a non-oriented graph. Cybernetics 22, 156-162.
• 42: Samir Khuller , Baruch Schieber, Efficient parallel algorithms for testing k-connectivity and finding disjoint s-t paths in graphs, SIAM Journal on Computing, v.20 n.2, p.352-375, April 1990 [doi>10.1137/0220022]
• 43: V. King , S. Rao , R. Tarjan, A faster deterministic maximum flow algorithm, Journal of Algorithms, v.17 n.3, p.447-474, Nov. 1994
• 44: Philip Klein , Serge Plotkin , Clifford Stein , Eva Tardos, Faster Approximation Algorithms for the Unit Capacity Concurrent Flow Problem with Applications to Routing and Finding Sparse Cuts, SIAM Journal on Computing, v.23 n.3, p.466-487, June 1994 [doi>10.1137/S0097539792241175]
• 45: Donald E. Knuth, The Art of Computer Programming Volumes 1-3 Boxed Set, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1998
• 46: KNUTH, D. E., AND YAO, A.E. 1976. The complexity of nonuniform random number generation. ~ In Algorithms and Complexity: New Directions and Recent Results, Joseph F. Traub, ed. Academic ~ Press, New York, pp. 357-428.
• 47: ICRUSKAL, JR., J.B. 1956. On the shortest spanning subtree of a graph and the traveling salesman ~ problem. Proc. AMS 7, 1, 48-50.
• 48: LAWLER, U. L., LENSTRA, J. K., RINOOY mAN, A. H. G., AND SHMOYS, D. B., EDS. 1985. The ~ Traveling Salesman Problem. Wiley, New York.
• 49: LOMONOSOV, M.V. 1994. On Monte Carlo estimates in network reliability. Prob. Eng. Inf. Sci. 8, ~ 245-264.
• 50: MADER, W. 1968. Homomorphiesiitze fiir graphen. Math. Ann. 178, 154-168.
• 51: ~MATULA, D.W. 1986. Determining edge connectivity in O(nm). In Proceedings of the 28th Annual ~ Symposium on the Foundations of Computer Science. IEEE Computer Society Press, pp. 249-251.
• 52: David W. Matula, A linear time 2 + &&egr; approximation algorithm for edge connectivity, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.500-504, January 25-27, 1993, Austin, Texas, United States
• 53: MULMULE~, K. 1994. Computational Geometry. Prentice-Hall, Englewood Cliffs, N.J.
• 54: K. Mulmuley , U. V. Vazirani , V. V. Vazirani, Matching is as easy as matrix inversion, Combinatorica, v.7 n.1, p.105-113, Jan. 1987 [doi>10.1007/BF02579206]
• 55: 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]
• 56: NAOR, D., AND VAZIRANI, V.V. 1991. Representing and enumerating edge connectivity cuts in ~ ~&Cqg. In Proceedings of the 2rid Workshop on Algorithms and Data Structures, F. Dehne, J. R. Sack, ~ and N. Santoro, eds. Lecture Notes in Computer Science, Vol. 519. Springer-Verlag, New York, pp. ~ 273-285.
• 57: 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]
• 58: Steven Phillips , Jeffery Westbrook, Online load balancing and network flow, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.402-411, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167201]
• 59: PICARD, J. C., AND QUEYRANNE, M. 1982. Selected applications of minimum cuts in networks. ~ I.N.F.O.R: Can. J. Oper. Res. Inf. Proc. 20, (Nov.), 394-422.
• 60: PICARD, J. C., AND RATLIFF, H. D. 1975. Minimum cuts and related problems. Networks 5, ~ 357-370.
• 61: PODDERYUGIN, V.D. 1973. An algorithm for finding the edge connectivity of graphs. Vopr. Kibern. ~ 2, 136.
• 62: RAMACHANDRAN, V. 1987. Flow value, minimum cuts and maximum flows. Manuscript.
• 63: Aparna Ramanathan , Charles J. Colbourn, Counting almost minimum cutsets with reliability applications, Mathematical Programming: Series A and B, v.39 n.3, p.253-261, December 1, 1987 [doi>10.1007/BF02592076]
• 64: SHILOACH, Y., AND VISHKIN, U. 1982. An O(log n) parallel connectivity algorithm. J. Algorithms 3, ~ 57-67.
• 65: 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]
• 66: Mechthild Stoer , Frank Wagner, A Simple Min Cut Algorithm, Proceedings of the Second Annual European Symposium on Algorithms, p.141-147, September 26-28, 1994
• 67: Robert Endre Tarjan, Data structures and network algorithms, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1983
• 68: 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
• 69: VON NEUMANN, J. 1951. Various techniques used in connection with random digits. Nat. Bur. ~ Stand. Appl. Math Ser. 12, 36-38.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms; Network problems
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms

General Terms:
Algorithms

Keywords:
graph algorithm, minimum cut, network reliability, parallel computing, randomized algorithm