Deterministic global minimum cut of a simple graph in near-linear time

TY - GEN

T1 - Deterministic global minimum cut of a simple graph in near-linear time

AU - Kawarabayashi, Ken-ichi

AU - Thorup, Mikkel

N1 - Conference code: 47

PY - 2015/6/14

Y1 - 2015/6/14

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

KW - deterministic near-linear time, edge connectivity, minimum cut, simple graphs

U2 - 10.1145/2746539.2746588

DO - 10.1145/2746539.2746588

M3 - Article in proceedings

SN - 978-1-4503-3536-2

SP - 665

EP - 674

BT - Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - Annual ACM Symposium on the Theory of Computing 2015

Y2 - 15 June 2015 through 17 June 2015

ER -