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.
| Originalsprog | Engelsk |
|---|---|
| Artikelnummer | 4 |
| Tidsskrift | Journal of the ACM |
| Vol/bind | 66 |
| Udgave nummer | 1 |
| Sider (fra-til) | 1-50 |
| ISSN | 0004-5411 |
| DOI | |
| Status | Udgivet - dec. 2018 |