We present a universally-optimal distributed algorithm for the exact weighted min-cut. The algorithm is guaranteed to complete in $\widetilde{O}(D + \sqrt{n})$ rounds on every graph, recovering the recent result of Dory, Efron, Mukhopadhyay, and Nanongkai~[STOC'21], but runs much faster on structured graphs. Specifically, the algorithm completes in $\widetilde{O}(D)$ rounds on (weighted) planar graphs or, more generally, any (weighted) excluded-minor family. We obtain this result by designing an aggregation-based algorithm: each node receives only an aggregate of the messages sent to it. While somewhat restrictive, recent work shows any such black-box algorithm can be simulated on any minor of the communication network. Furthermore, we observe this also allows for the addition of (a small number of) arbitrarily-connected virtual nodes to the network. We leverage these capabilities to design a min-cut algorithm that is significantly simpler compared to prior distributed work. We hope this paper showcases how working within this paradigm yields simple-to-design and ultra-efficient distributed algorithms for global problems. Our main technical contribution is a distributed algorithm that, given any tree $T$, computes the minimum cut that $2$-respects $T$ (i.e., cuts at most $2$ edges of $T$) in universally near-optimal time. Moreover, our algorithm gives a \emph{deterministic} $\widetilde{O}(D)$-round 2-respecting cut solution for excluded-minor families and a \emph{deterministic} $\widetilde{O}(D + \sqrt{n})$-round solution for general graphs, the latter resolving a question of Dory, et al.~[STOC'21]
翻译:我们为精确加权的刻度提出了一个普遍最优化分布的算法 。 算法保证在每张图上以$+\\ sqrt{( D +\ sqrt{ n}) 以美元完成, 恢复Dory、 Efron、 Mukhopadhyay 和 Nanongkai 最近的结果, 在结构化的图表上运行速度要快得多 。 具体地说, 算法在( 重量级) 平面图上以$- 美元( D) 回合完成。 我们通过设计一个基于总基数的算算法( 加权) 来完成这个结果: 每个节数只收到发给它的信件的总数。 虽然有些限制性, 最近的工作显示任何这样的黑盒算法都可以模拟通信网络的任何小部分 。 此外, 我们观察这也允许在网络上添加( 少量) 任意连接的虚拟点数 。 我们利用这些能力来设计一个比先前分配的 $ 美元 更简单的刻度算法 。 我们希望, 在最接近时间 的平面上, 文件会展示我们最简单的算法是如何将多少 。