论文标题
小顶点切割的近乎最佳分布计算
Near-Optimal Distributed Computation of Small Vertex Cuts
论文作者
论文摘要
我们提出了近乎最佳的算法，用于检测分布式计算的交通拥堵模型中的小顶点切割。尽管在这一领域进行了广泛的研究，但我们对图形的顶点连接性的理解仍然不完整，尤其是在分布式环境中。到目前为止，所有用于检测切割顶点的分布式算法都属于图最大程度的固有依赖性，即$δ$。因此，尤其是，对于此问题，没有真正的子线性时间算法，甚至没有检测到单切顶点。我们采用了一种新的算法方法，以实现顶点连接性，这使我们能够绕过现有的$δ$屏障。作为对我们方法的热身，我们显示了一个简单的$ \ widetilde {o}（d）$ - 圆形随机算法，用于计算$ d $ -d $ diameter $ n $ n $ vertex图中的所有剪切顶点。这在[Pritchard and Thurimella，ICALP 2008]的$ O（D+δ/\ log N）$ - 圆形算法上有所改善。我们的关键技术贡献是用于计算图中所有剪切对的$ \ widetilde {o}（d）$ - 圆形随机算法，可改善最先进的$ O（δ\ cdot d）^4 $ Round算法[PARTER，DISS '19]。请注意，即使对于更简单的边缘切割设置，当前$ \ widetilde {o}（d）$ - 圆形算法仅用于检测切割边缘对。我们的方法基于采用众所周知的线性图草图技术[Ahn，Guha和McGregor，Soda 2012]以及[Sleator和Tarjan，STOC 1981]的重型树的分解。将其与可生存子图的仔细表征结合在一起，使我们能够使用$ \ wideTilde {o}（o}（o}（d）$ - 回合，每对$ x，y \ in V $的$ g \ setMinus \ {x，y \} $的连接性。我们认为，本文提供的工具对于省略$δ$依赖性也很有用，即使对于更大的剪切值也是如此。
We present near-optimal algorithms for detecting small vertex cuts in the CONGEST model of distributed computing. Despite extensive research in this area, our understanding of the vertex connectivity of a graph is still incomplete, especially in the distributed setting. To this date, all distributed algorithms for detecting cut vertices suffer from an inherent dependency in the maximum degree of the graph, $Δ$. Hence, in particular, there is no truly sub-linear time algorithm for this problem, not even for detecting a single cut vertex. We take a new algorithmic approach for vertex connectivity which allows us to bypass the existing $Δ$ barrier. As a warm-up to our approach, we show a simple $\widetilde{O}(D)$-round randomized algorithm for computing all cut vertices in a $D$-diameter $n$-vertex graph. This improves upon the $O(D+Δ/\log n)$-round algorithm of [Pritchard and Thurimella, ICALP 2008]. Our key technical contribution is an $\widetilde{O}(D)$-round randomized algorithm for computing all cut pairs in the graph, improving upon the state-of-the-art $O(Δ\cdot D)^4$-round algorithm by [Parter, DISC '19]. Note that even for the considerably simpler setting of edge cuts, currently $\widetilde{O}(D)$-round algorithms are known only for detecting pairs of cut edges. Our approach is based on employing the well-known linear graph sketching technique [Ahn, Guha and McGregor, SODA 2012] along with the heavy-light tree decomposition of [Sleator and Tarjan, STOC 1981]. Combining this with a careful characterization of the survivable subgraphs, allows us to determine the connectivity of $G \setminus \{x,y\}$ for every pair $x,y \in V$, using $\widetilde{O}(D)$-rounds. We believe that the tools provided in this paper are useful for omitting the $Δ$-dependency even for larger cut values.
