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 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. A preliminary version [22] was presented at the 47th ACM Symposium on Theory of Computing (STOC 2015). Deterministic Edge Connectivity in Near-Linear Time 4:3 268-269] also discuss multigraphs with a slightly worse bound of O (m + λ 2 n log n). A linear time (2 + ε)-approximation of the edge-connectivity was presented by Matula [24] . All the above-mentioned algorithms have been deterministic. The study of randomized algorithms for the global minimum cut problem was initiated by Karger [17] . We distinguish between Las Vegas algorithms with guaranteed correct answers but expected running times, and Monte Carlo algorithms with bounded running time but some small probability of incorrect answers. Las Vegas algorithms can be converted to Monte Carlo algorithms (making an error if the algorithm doesn't terminate within a certain time bound), so Las Vegas is generally preferred. If we have a way to certify correct answers, then we can also convert Monte Carlo to Las Vegas by rerunning if the certifyer fails. Karger [17] presented Las Vegas algorithms yeilding a (1 + o(1))-approximation to the global minimum cut in O (m) expected time and an exact global minimum cut in O (m √ λ) expected time. Karger and Stein [20] showed that random edge contraction works well for the global minimum cut problem, leading to a Monte Carlo algorithm running in O (n 2 log 3 n) time. Finally, Karger [18] gave a randomized O (m log 3 n) time Monte Carlo algorithm for the global minimum cut problem. Karger [18] points out that we are lacking a correspondingly efficient way to certify the minimality of the returned cut. For more detailed history for the global minimum cut problem, we refer the reader to the book by Schrijver [29] . We note that a deterministic near-linear time min-cut algorithm is known for planar graphs [4]. In this article, we present a deterministic near-linear time algorithm for computing the edge connectivity and a global minimum cut for a simple graph. By near-linear time, we mean O (m) time where O hides log factors. This is the first o(mn) time deterministic algorithm for the problem. The previous best O (m + λ 2 n) time bound of Gabow [9] is good if λ is small, but we may have λ = Ω(n). We note that in this article, we are not trying to minimize the number of log factors hidden in the O-notation, nor do we count them explicitely, e.g., we will freely use reductions like O ( f (n)) O (д(n)) = O ( f (n)д(n)). At the end, we will loosely estimate the number to 12, thus estimating the running time of our algorithm to O (m log 12 n). The purpose of this estimate is only to encourage other researchers to get down to a more reasonable number of log factors, providing them a concrete bound to improve on. Indeed, Henzinger et al. [14] have recently improved important parts of our construction bringing the total running time down to O (m(log n) 2 (log log n) 2 ). In near-linear time, we can also compute the cactus representation of all global minimum cuts introduced in Reference [5]. To do so, we involve the previous fastest O (λm) time algorithm by Gabow [10] as a black-box. We note here that Karger and Panigrahi [19] have presented a nearlinear time Monte Carlo algorithm for constructing the cactus data structure. Henceforth, we are only considering unweighted graphs. We are given a simple graph, and we want to find a min-cut in near-linear time. We may assume that the minimum degree δ is at least polylogarithmic; for otherwise, we can just use Gabow's [9], algorithm to find the min-cut in O (λm) = O (δm) = O (m) time. For our purposes, it suffices to assume δ ≥ log 6 n. By a trivial cut, we mean a cut where one side consists of a single vertex. We note that the minimum degree δ is an upper bound on the edge-connectivity λ, since it is the smallest size of a trivial cut. Finding δ is trivial, but we could have λ < δ . What makes simple graphs special is that if you have a non-trivial cut in a simple graph, then each side needs to have at least δ vertices. This observation and its relation to conductance will be discussed below in Section 1.4. By contracting a vertex set U ⊆ V , we mean identifying the vertices in U while removing the edges between them. We may not check that U is connected, so this may not correspond to edge contractions. The identity of edges not removed are preserved, and a cut is preserved if all the cut edges are preserved. The basic idea in our min-cut algorithm is do contractions in the graph while preserving all non-trivial min-cuts, continuing until the graph is so small that Gabow's algorithm can finish in O (m) time, where m is the number of edges in the original simple input graph. The contractions may introduce parallel edges, so internally, the algorithm works with a multigraph. Our main technical contribution is to prove the following theorem: Theorem 1.1. Given a simple input graph G with n vertices, m edges, and minimum degree δ , in near-linear time, we can contract vertex sets producing a multigraph G, which has only m = O (m/δ ) edges, yet which preserves all non-trivial min-cuts of G. From Theorem 1.1, we easily get our near-linear min-cut algorithm: Corollary 1.2. We can find a minimum cut of a simple graph G in near-linear time. Proof. Let δ be the minimum degree of G. We apply the Theorem 1.1 to G producing the graph G. We now run Gabow's min-cut algorithm [9] on G, asking it to fail if the edge-connectivity is above δ . This takes O (δm) = O (m) time, and now we compare the output with the minimum degree δ . Likewise, in near-linear time, we can obtain the cactus representation of all global minimum cuts from Reference [5] by applying the cactus algorithm of Gabow [10] to G. Having produced the cactus C of G, we just need to add min-degree vertices as extra needles to get the cactus of the input graph G. A description of this including the definition of the min-cut cactus is given in Section 8. We note that Theorem 1.1 cannot hold if the input graph is a multigraph. To see this, consider a cycle of length n ≥ 4, but where every edge is replaced by k = (log n) ω (1) parallel edges. Now every edge is involved in a non-trivial min-cut where each side consists of at least two consecutive vertices, and therefore no edges can be contracted. This shows that the contractions of Theorem 1.1 are very specific to simple graphs. Also, they can only preserve non-trivial min-cuts, for if we, for example, take a complete graph, then every edge is in a trivial min-cut. However, a complete graph can be contracted to a single vertex, since it has no non-trivial min-cut. Further Results. While the reduction in Theorem 1.1 of the number of edges looks like a typical sparsification, it is not, for edges are contracted, not deleted, and the resulting G will have much fewer vertices than G. In fact, combining with techniques of Nagamochi and Ibaraki [27], we can make sure that the number of vertices remaining after the contractions is O (n/δ ). Since the number of min-cuts in any multigraph is at most quadratic, a nice consequence is that that the number of min-cuts in a simple graph with n vertices and minimum degree δ is at most n + O ((n/δ ) 2 ). We are not aware of anyone else that has observed that a large minimum degree in a simple graph implies few minimum cuts, though it does appear that this fact could also be derived from the cactus representation [5] . Our contraction technique can be strengthened to also preserve approximately min-cuts. More precisely, with min-degree δ and edge connectivity λ, we will strengthen Theorem 1.1 to
This technique was introduced by Kawarabayashi and Thorup REF , who achieve near-linear deterministic time (estimated to be O(m log 12 n)).
Deterministic Edge Connectivity in Near-Linear Time
JACM
Computer Science Mathematics