Optimal Bounds for the k -cut Problem
Optimal Bounds for the k -cut Problem
复制标题
k 割问题的最优界
DOI：
10.1145/3478018
复制
发表时间：
2022
影响因子：
2.5
通讯作者：
Li, Jason
中科院分区：
文献类型：
--
作者：
Gupta, Anupam;Harris, David G.;Lee, Euiwoong;Li, Jason
在k-cut问题中，我们希望找到最低权重的边集，这些边的删除将给定的（多）图破坏为k连通分量。Karger和Stein的算法可以在大约O（n2 k）时间内解决这个问题。然而，k-团问题的解的下界意味着可能需要Ω（n（1-o（1））k）时间. Gupta，Lee和Li最近的结果给出了1.98k + O（1）时间的一般割算法，以及对某些类图具有更好性能的专门算法（例如，在这项工作中，我们解决了一般图的问题。本文证明了Karger的收缩算法以概率Ωk（n-αk）输出权α λ k的任意固定k-割，其中λ k表示最小k-割权。这也给出了Ok（nk）关于最小k-割数的极值界和一个计算λ k的算法，运行时间为粗略的lynkpolylog（n）。这两个算法都是紧到低阶因子的，算法的下界假设最大权重k-团的硬度。我们结果中的第一个主要成分是使用向日葵引理得到的关于权重小于2 λk/k的切割数的极值界。第二个要素是对Karger过程中图形如何收缩以及平均度如何演变的细粒度分析。
In thek-cut problem, we want to find the lowest-weight set of edges whose deletion breaks a given (multi)graph intokconnected components. Algorithms of Karger and Stein can solve this in roughlyO(n2k) time. However, lower bounds from conjectures about thek-clique problem imply that Ω (n(1-o(1))k) time is likely needed. Recent results of Gupta, Lee, and Li have given new algorithms for generalk-cut inn1.98k + O(1)time, as well as specialized algorithms with better performance for certain classes of graphs (e.g., for small integer edge weights).In this work, we resolve the problem for general graphs. We show that the Contraction Algorithm of Karger outputs any fixedk-cut of weight α λkwith probability Ωk(n-αk), where λkdenotes the minimumk-cut weight. This also gives an extremal bound ofOk(nk) on the number of minimumk-cuts and an algorithm to compute λkwith roughlynkpolylog(n) runtime. Both are tight up to lower-order factors, with the algorithmic lower bound assuming hardness of max-weightk-clique.The first main ingredient in our result is an extremal bound on the number of cuts of weight less than 2 λk/k, using the Sunflower lemma. The second ingredient is a fine-grained analysis of how the graph shrinks—and how the average degree evolves—in the Karger process.