A new approach to the minimum cut problem

This paper presents 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(n(2)log(3)n) time, a significant improvement over the previous (O) over tilde(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 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 cu of the minimum cut's in expected (O) over tilde(n(2 alpha)) time, or in RNC with n(2 alpha) processors. The problem of finding a minimum multiway cut of a graph into r pieces is solved in expected (O) over tilde(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.