论文标题
分布式加权最低限度在几乎最佳时间内
Distributed Weighted Min-Cut in Nearly-Optimal Time
论文作者
论文摘要
最小重量切割（最小切割）是网络连接强度的基本量度。虽然可以在顺序设置[Karger Stoc'96]中有效地计算最小的切割，但分布式网络没有有效的方法来计算自己的最小切割，而无需限制输入结构或删除输出质量：在标准的CONCEST模型中，现有的算法在现有的算法中，几乎恰当的时间确定了[ghaffari，su disce's disce's disce's discond;解决方案是$（1 +ε）$ - 最多近似，而确切的$ \ tilde o（n^{0.8} d^{0.2} + n^{0.9}）$ - 时间算法[ghaffari，nowicki，nowicki，nowicki，thorup，soda'20]仅在 *简单的 *网络上起作用（无权重，无平行edges）。在这里，$ n $和$ d $分别表示网络的顶点和跳直径。对于加权案例，最好的绑定是$ \ tilde o（n）$ [Daga，Henzinger，Nanongkai，Saranurak，Stoc'19]。 在本文中，我们提供了一个 * exack * $ \ tilde o（\ sqrt n + d）$ - 用于计算“加权 *网络”上的最小算法的时间算法。我们的结果甚至可以改善仅在简单网络上起作用的算法。它的时间复杂性与已知的下限与多毛体因子相匹配。我们算法的核心是一个巧妙的路由技巧，并且关于图最小切割的结构的两个结构引理。这两个结构引理大大增强了Mukhopadhyay-Nanongkai [stoc'20]的框架，并具有独立的利益。
Minimum-weight cut (min-cut) is a basic measure of a network's connectivity strength. While the min-cut can be computed efficiently in the sequential setting [Karger STOC'96], there was no efficient way for a distributed network to compute its own min-cut without limiting the input structure or dropping the output quality: In the standard CONGEST model, existing algorithms with nearly-optimal time (e.g. [Ghaffari, Kuhn, DISC'13; Nanongkai, Su, DISC'14]) can guarantee a solution that is $(1+ε)$-approximation at best while the exact $\tilde O(n^{0.8}D^{0.2} + n^{0.9})$-time algorithm [Ghaffari, Nowicki, Thorup, SODA'20] works only on *simple* networks (no weights and no parallel edges). Here $n$ and $D$ denote the network's number of vertices and hop-diameter, respectively. For the weighted case, the best bound was $\tilde O(n)$ [Daga, Henzinger, Nanongkai, Saranurak, STOC'19]. In this paper, we provide an *exact* $\tilde O(\sqrt n + D)$-time algorithm for computing min-cut on *weighted* networks. Our result improves even the previous algorithm that works only on simple networks. Its time complexity matches the known lower bound up to polylogarithmic factors. At the heart of our algorithm are a clever routing trick and two structural lemmas regarding the structure of a minimum cut of a graph. These two structural lemmas considerably strengthen and generalize the framework of Mukhopadhyay-Nanongkai [STOC'20] and can be of independent interest.
