Abstract
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.
| Original language | English |
|---|---|
| Article number | 4 |
| Journal | Journal of the ACM |
| Volume | 66 |
| Issue number | 1 |
| Pages (from-to) | 1-50 |
| ISSN | 0004-5411 |
| DOIs | |
| Publication status | Published - Dec 2018 |