We consider the minimum cut problem in undirected, weighted graphs. We give a simple algorithm to find a minimum cut that @math -respects (cuts two edges of) a spanning tree @math of a graph @math . This procedure can be used in place of the complicated subroutine given in Karger's near-linear time minimum cut algorithm (J. ACM, 2000). We give a self-contained version of Karger's algorithm with the new procedure, which is easy to state and relatively simple to implement. It produces a minimum cut on an @math -edge, @math -vertex graph in @math time with high probability. This performance matches that achieved by Karger, thereby matching the current state of the art.
On an unweighted graph, Gabow @cite_13 showed how to compute the minimum cut in @math time, where @math is the capacity of the minimum cut. Karger @cite_29 improved Gabow's algorithm by applying random sampling, achieving runtime @math The @math notation hides @math factors. Las Vegas. The sampling technique developed by Karger @cite_29 , combined with the tree-packing technique devised by Gabow @cite_13 , form the basis of Karger's near-linear time minimum cut algorithm @cite_16 . As previously mentioned, this technique finds the minimum cut in an undirected, weighted graph in @math time with high probability.
@cite_29 @cite_16 @cite_13
2064493067 2963972775 1964510837 1543491698
We present a deterministic near-linear time algorithm that computes the edge-connectivity and finds a minimum cut for a simple undirected unweighted graph G with n vertices and m edges. This is the first o(mn) time deterministic algorithm for the problem. In near-linear time we can also construct the classic cactus representation of all minimum cuts. The previous fastest deterministic algorithm by Gabow from STOC'91 took O(m+λ2 n), where λ is the edge connectivity, but λ could be Ω(n). At STOC'96 Karger presented a randomized near linear time Monte Carlo algorithm for the minimum cut problem. As he points out, there is no better way of certifying the minimality of the returned cut than to use Gabow's slower deterministic algorithm and compare sizes. Our main technical contribution is a near-linear time algorithm that contracts vertex sets of a simple input graph G with minimum degree δ, producing a multigraph G with O(m δ) edges which preserves all minimum cuts of G with at least two vertices on each side. In our deterministic near-linear time algorithm, we will decompose the problem via low-conductance cuts found using PageRank a la Brin and Page (1998), as analyzed by Andersson, Chung, and Lang at FOCS'06. Normally such algorithms for low-conductance cuts are randomized Monte Carlo algorithms, because they rely on guessing a good start vertex. However, in our case, we have so much structure that no guessing is needed. We present a deterministic algorithm that computes the edge-connectivity of a graph in near-linear time. This is for a simple undirected unweighted graph G with n vertices and m edges. This is the first o(mn) time deterministic algorithm for the problem. Our algorithm is easily extended to find a concrete minimum edge-cut. In fact, we can construct the classic cactus representation of all minimum cuts in near-linear time. The previous fastest deterministic algorithm by Gabow from STOC '91 took O(m+λ2 n), where λ is the edge connectivity, but λ can be as big as n−1. Karger presented a randomized near-linear time Monte Carlo algorithm for the minimum cut problem at STOC’96, but the returned cut is only minimum with high probability. Our main technical contribution is a near-linear time algorithm that contracts vertex sets of a simple input graph G with minimum degree Δ, producing a multigraph Ḡ with O(m Δ) edges, which preserves all minimum cuts of G with at least two vertices on each side. In our deterministic near-linear time algorithm, we will decompose the problem via low-conductance cuts found using PageRank a la Brin and Page (1998), as analyzed by Andersson, Chung, and Lang at FOCS’06. Normally, such algorithms for low-conductance cuts are randomized Monte Carlo algorithms, because they rely on guessing a good start vertex. However, in our case, we have so much structure that no guessing is needed. 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 log 3 n ) time. We also give a simpler randomized algorithm that finds all minimum cuts with high probability in O( m log 3 n ) time. This variant has an optimal RNC parallelization. Both variants improve on the previous best time bound of O ( n 2 log 3 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. We describe random sampling techniques for approximately solving problems that involve cuts and flows in graphs. We give a near-linear-time randomized combinatorial construction that transforms any graph on @math vertices into an @math -edge graph on the same vertices whose cuts have approximately the same value as the original graph's. In this new graph, for example, we can run the @math -time maximum flow algorithm of Goldberg and Rao to find an @math - @math minimum cut in @math time. This corresponds to a @math -times minimum @math - @math cut in the original graph. A related approach leads to a randomized divide-and-conquer algorithm producing an approximately maximum flow in @math time. Our algorithm can also be used to improve the running time of sparsest cut approximation algorithms from @math to @math and to accelerate several other recent cut and flow algorithms. Our algorithms are based on a general theorem analyzing the concent...