Deterministic Edge Connectivity in Near-Linear Time

TY - JOUR

T1 - Deterministic Edge Connectivity in Near-Linear Time

AU - Kawarabayashi, Ken-ichi

AU - Thorup, Mikkel

PY - 2018/12

Y1 - 2018/12

N2 - 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.

AB - 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.

U2 - 10.1145/3274663

DO - 10.1145/3274663

M3 - Journal article

SN - 0004-5411

VL - 66

SP - 1

EP - 50

JO - Journal of the ACM

JF - Journal of the ACM

IS - 1

M1 - 4

ER -