论文标题
动态流中顶点连接的紧密界限
Tight Bounds for Vertex Connectivity in Dynamic Streams
论文作者
论文摘要
我们提出了一种在动态流中的顶点连接问题的流算法，具有（几乎）最佳空间绑定：对于任何$ n $ vertex graph $ g $和任何Integer $ k \ geq 1 $，我们的算法，具有高概率输出的算法，无论$ g $是$ k $ k $ k $ k $ - vertex-contection $ vertex-contection $ n passe $ b n passe $ \ n passectect y passectield $ \ b n of b n） 即使在仅插入流中，我们的上限也与已知的$ω（k n）$下限匹配了此问题的下限 - 我们将其扩展到本文中的多通算法 - 并缩小了我们对动态与插入流的理解中的最后剩余差距之一。我们的结果是通过对Guha，McGregor和Tench [Pods 2015]的先前最佳动态流算法的新颖分析而获得的，后者获得了此问题的$ \ widetilde {o}（k^2 N）$ space算法。这还提供了一种独立于模型的算法，用于计算$ k $ - vertex-connectitive的“证书”作为$ O（k^2 \ log {n}）$跨越森林的结合，每个$ spanning Forests $（n/k）$ Vertices的随机子集，这可能是独立的。
We present a streaming algorithm for the vertex connectivity problem in dynamic streams with a (nearly) optimal space bound: for any $n$-vertex graph $G$ and any integer $k \geq 1$, our algorithm with high probability outputs whether or not $G$ is $k$-vertex-connected in a single pass using $\widetilde{O}(k n)$ space. Our upper bound matches the known $Ω(k n)$ lower bound for this problem even in insertion-only streams -- which we extend to multi-pass algorithms in this paper -- and closes one of the last remaining gaps in our understanding of dynamic versus insertion-only streams. Our result is obtained via a novel analysis of the previous best dynamic streaming algorithm of Guha, McGregor, and Tench [PODS 2015] who obtained an $\widetilde{O}(k^2 n)$ space algorithm for this problem. This also gives a model-independent algorithm for computing a "certificate" of $k$-vertex-connectivity as a union of $O(k^2\log{n})$ spanning forests, each on a random subset of $O(n/k)$ vertices, which may be of independent interest.
