Journal of the Association for Computing Machinery, Vol. 43, No. 4, July 1996, pp. 601–640.

A New Approach to the Minimum Cut Problem

DAVID R. KARGER

AND

CLIFFORD STEIN

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 Õ(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 RN C with n^{2} processors; this gives the first proof that the minimum cut problem can be solved in RN C. 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 α of the minimum cut’s in expected Õ(n^{2α}) time, or in RN C with n^{2α} processors. The problem of finding a minimum multiway cut of a graph into r pieces is solved in expected Õ(n^{2(r−1)}) time, or in RN C 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.

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

Copyright 1996 by ACM, Inc. Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or direct commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, to republish, to post on servers, or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from Publications Dept, ACM Inc., fax +1 (212) 869-0481, or permissions@acm.org.