TY - GEN

T1 - The Karger-Stein algorithm is optimal for k-cut

AU - Gupta, Anupam

AU - Lee, Euiwoong

AU - Li, Jason

N1 - Publisher Copyright:
© 2020 ACM.

PY - 2020/6/8

Y1 - 2020/6/8

N2 - In the k-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. Algorithms due to Karger-Stein and Thorup showed how to find such a minimum k-cut in time approximately O(n2k-2). The best lower bounds come from conjectures about the solvability of the k-clique problem and a reduction from k-clique to k-cut, and show that solving k-cut is likely to require time ω(nk). Our recent results have given special-purpose algorithms that solve the problem in time n1.98k + O(1), and ones that have better performance for special classes of graphs (e.g., for small integer weights). In this work, we resolve the problem for general graphs, by showing that for any fixed k ≥ 2, the Karger-Stein algorithm outputs any fixed minimum k-cut with probability at least O(n-k), where O(·) hides a 2O(lnlnn)2 factor. This also gives an extremal bound of O(nk) on the number of minimum k-cuts in an n-vertex graph and an algorithm to compute a minimum k-cut in similar runtime. Both are tight up to O(1) factors. The first main ingredient in our result is a fine-grained analysis of how the graph shrinks - and how the average degree evolves - under the Karger-Stein process. The second ingredient is an extremal result bounding the number of cuts of size at most (2-) OPT/k, using the Sunflower lemma.

AB - In the k-cut problem, we are given an edge-weighted graph and want to find the least-weight set of edges whose deletion breaks the graph into k connected components. Algorithms due to Karger-Stein and Thorup showed how to find such a minimum k-cut in time approximately O(n2k-2). The best lower bounds come from conjectures about the solvability of the k-clique problem and a reduction from k-clique to k-cut, and show that solving k-cut is likely to require time ω(nk). Our recent results have given special-purpose algorithms that solve the problem in time n1.98k + O(1), and ones that have better performance for special classes of graphs (e.g., for small integer weights). In this work, we resolve the problem for general graphs, by showing that for any fixed k ≥ 2, the Karger-Stein algorithm outputs any fixed minimum k-cut with probability at least O(n-k), where O(·) hides a 2O(lnlnn)2 factor. This also gives an extremal bound of O(nk) on the number of minimum k-cuts in an n-vertex graph and an algorithm to compute a minimum k-cut in similar runtime. Both are tight up to O(1) factors. The first main ingredient in our result is a fine-grained analysis of how the graph shrinks - and how the average degree evolves - under the Karger-Stein process. The second ingredient is an extremal result bounding the number of cuts of size at most (2-) OPT/k, using the Sunflower lemma.

KW - Graph Algorithms

KW - Minimum Cut

KW - Randomized Algorithms

UR - http://www.scopus.com/inward/record.url?scp=85086755987&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85086755987&partnerID=8YFLogxK

U2 - 10.1145/3357713.3384285

DO - 10.1145/3357713.3384285

M3 - Conference contribution

AN - SCOPUS:85086755987

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 473

EP - 484

BT - STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing

A2 - Makarychev, Konstantin

A2 - Makarychev, Yury

A2 - Tulsiani, Madhur

A2 - Kamath, Gautam

A2 - Chuzhoy, Julia

PB - Association for Computing Machinery

T2 - 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020

Y2 - 22 June 2020 through 26 June 2020

ER -