In the $k$-cut problem, we want to find the lowest-weight set of edges whose deletion breaks a given (multi)graph into $k$ connected components. Algorithms of Karger \& Stein can solve this in roughly $O(n^{2k})$ time. On the other hand, lower bounds from conjectures about the $k$-clique problem imply that $\Omega(n^{(1-o(1))k})$ time is likely needed. Recent results of Gupta, Lee \& Li have given new algorithms for general $k$-cut in $n^{1.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 fixed $k$-cut of weight $\alpha \lambda_k$ with probability $\Omega_k(n^{-\alpha k})$, where $\lambda_k$ denotes the minimum $k$-cut weight. This also gives an extremal bound of $O_k(n^k)$ on the number of minimum $k$-cuts and an algorithm to compute $\lambda_k$ with roughly $n^k \mathrm{polylog}(n)$ runtime. Both are tight up to lower-order factors, with the algorithmic lower bound assuming hardness of max-weight $k$-clique. The first main ingredient in our result is an extremal bound on the number of cuts of weight less than $2 \lambda_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.


翻译:在 $k$- clotique 问题中, 我们想要找到最低重量的边缘, 其删除将给定的( 倍数) 折成 $ k美元 连接的元件。 Karger 的 Algorithms 能够用大约 $( n ⁇ 2k}) 美元的时间解决这个问题。 另一方面, 有关 $k$- clodique 问题的测算的下限意味着可能需要 $\\\\ ⁇ ( 1- o(1) k} ) 美元 。 最近的 Gupta 的结果, Lee Lee 已经给出了通用美元( 倍数) 的新的算法 $- 美元( 美元) 美元 。 美元=1. 98k + O(1) 美元 时间, 某些图表类别( 例如, 小整数的边数), 我们解决了一般图表的问题。 我们显示, Karger 输出的Alegorthmion Alorth m 任何固定美元重量的计算 $\ al- 。 (alda) modealda) a more diral deal deal deal deal a $_ leglegal $_ $.

0
下载
关闭预览

相关内容

Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
【课程】纽约大学 DS-GA 1003 Machine Learning
专知会员服务
45+阅读 · 2019年10月29日
Stabilizing Transformers for Reinforcement Learning
专知会员服务
58+阅读 · 2019年10月17日
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
已删除
将门创投
4+阅读 · 2019年10月11日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
Nearly Optimal Algorithms for Level Set Estimation
Arxiv
0+阅读 · 2021年11月2日
Arxiv
3+阅读 · 2017年12月1日
VIP会员
相关资讯
【论文笔记】通俗理解少样本文本分类 (Few-Shot Text Classification) (1)
深度学习自然语言处理
7+阅读 · 2020年4月8日
已删除
将门创投
4+阅读 · 2019年10月11日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Unsupervised Learning via Meta-Learning
CreateAMind
41+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
【推荐】YOLO实时目标检测(6fps)
机器学习研究会
20+阅读 · 2017年11月5日
[DLdigest-8] 每日一道算法
深度学习每日摘要
4+阅读 · 2017年11月2日
【推荐】免费书(草稿):数据科学的数学基础
机器学习研究会
20+阅读 · 2017年10月1日
Top
微信扫码咨询专知VIP会员