The minimum cut problem for an undirected edge-weighted graph asks us to divide its set of nodes into two blocks while minimizing the weighted sum of the cut edges. In this paper, we engineer the fastest known exact algorithm for the problem. State-of-the-art algorithms like the algorithm of Padberg and Rinaldi or the algorithm of Nagamochi, Ono and Ibaraki identify edges that can be contracted to reduce the graph size such that at least one minimum cut is maintained in the contracted graph. Our algorithm achieves improvements in running time over these algorithms by a multitude of techniques. First, we use a recently developed fast and parallel inexact minimum cut algorithm to obtain a better bound for the problem. Afterwards, we use reductions that depend on this bound to reduce the size of the graph much faster than previously possible. We use improved data structures to further lower the running time of our algorithm. Additionally, we parallelize the contraction routines of Overall, we arrive at a system that significantly outperforms the fastest state-of-the-art solvers for the exact minimum cut problem.
We review algorithms for the global minimum cut and related problems. A closely related problem is the problem, which asks for a minimum cut with nodes @math and @math in different partitions. Ford and Fulkerson @cite_31 proved that minimum @math - @math -cut is equal to maximum @math - @math -flow. Gomory and Hu @cite_11 observed that the (global) minimum cut can be computed with @math minimum @math - @math -cut computations. For the following decades, this result by Gomory and Hu was used to find better algorithms for global minimum cut using improved maximum flow algorithms @cite_16 . One of the fastest known maximum flow algorithms is the push-relabel algorithm @cite_23 by Goldberg and Tarjan.
@cite_31 @cite_16 @cite_23 @cite_11
2122466336 2113137767 2095284441 2005944337
Two simple approximation algorithms for the minimum @math -cut problem are presented. Each algorithm finds a @math cut having weight within a factor of @math of the optimal. One of our algorithms is particularly efficient---it requires a total of only @math maximum flow computations for finding a set of near-optimal @math cuts, one for each value of @math between 2 and @math . Minimum cut maximum flow algorithms on graphs have emerged as an increasingly useful tool for exactor approximate energy minimization in low-level vision. The combinatorial optimization literature provides many min-cut max-flow algorithms with different polynomial time complexity. Their practical efficiency, however, has to date been studied mainly outside the scope of computer vision. The goal of this paper is to provide an experimental comparison of the efficiency of min-cut max flow algorithms for applications in vision. We compare the running times of several standard algorithms, as well as a new algorithm that we have recently developed. The algorithms we study include both Goldberg-Tarjan style "push -relabel" methods and algorithms based on Ford-Fulkerson style "augmenting paths." We benchmark these algorithms on a number of typical graphs in the contexts of image restoration, stereo, and segmentation. In many cases, our new algorithm works several times faster than any of the other methods, making near real-time performance possible. An implementation of our max-flow min-cut algorithm is available upon request for research purposes. We consider the problem of finding the minimum capacity cut in a network G with n nodes. This problem has applications to network reliability and survivability and is useful in subroutines for other network optimization problems. One can use a maximum flow problem to find a minimum cut separating a designated source node s from a designated sink node t, and by varying the sink node one can find a minimum cut in G as a sequence of at most 2n - 2 maximum flow problems. We then show how to reduce the running time of these 2n - 2 maximum flow algorithms to the running time for solving a single maximum flow problem. The resulting running time is O(nm log n 2 m) for finding the minimum cut in either a directed or undirected network. The algorithm also determines the arc connectivity of either a directed or undirected network in O(nm) steps. Given a finite undirected graph with nonnegative edge capacities the minimum capacity cut problem consists of partitioning the graph into two nonempty sets such that the sum of the capacities of edges connecting the two parts is minimum among all possible partitionings. The standard algorithm to calculate a minimum capacity cut, due to Gomory and Hu (1961), runs in O(n4) time and is difficult to implement. We present an alternative algorithm with the same worst-case bound which is easier to implement and which was found empirically to be far superior to the standard algorithm. We report computational results for graphs with up to 2000 nodes.