论文标题
跨越树计算的流式复杂性
Streaming Complexity of Spanning Tree Computation
论文作者
论文摘要
半流模型是经常用于计算图问题的流模型的变体。它允许使用$ \ tilde {o}（n）$ space在$ p $ passes中顺序读取$ n $节点输入图的边缘。在此模型中，可以在单个通行证中精确解决一些图形问题，例如跨越树和$ k $ - 连接性。尽管已知其他图形问题（例如三角检测和未加权的全对路径）需要$ \tildeΩ（n）$通过才能计算。对于许多基本的图形问题，这些模型中的障碍性是开放的。在本文中，我们研究了计算一些标准跨越树的障碍。我们的结果是： （1）最大叶子跨越树。已知此问题是apx完整的，而[245/244,2）$ in [245/244,2）$中的不合适性常数$ρ\。通过构建$ \ varepsilon $ -MLST Sparsifier，我们表明，对于每个常数$ \ varepsilon> 0 $，MLST可以在单个通行证中近似于$ 1+\ varepsilon $ W.H.P. （尽管在$ \ varepsilon \ leρ-1 $中以$ \ mathrm {p} \ ne \ ne \ mathrm {np} $的$ \ varepsilon \leρ-1 $中的超级顺序时间）。 （2）BFS树。众所周知，BFS树需要$ω（1）$通过才能计算，但是幼稚的方法需要$ o（n）$通过。我们设计了一种新的随机算法，该算法将通行复杂性降低到$ o（\ sqrt {n}）$，并且在通行证复杂性和空间用法之间提供了平稳的权衡。 （3）DFS树。 Khan and Mehta {[} STACS 2019 {]}的当前最佳算法采用$ \ tilde {o}（h）$ passes，其中$ h $是计算的DFS树的高度。我们的贡献是双重的。首先，我们通过与$ k $ node-contectitive的稀疏证书的新连接提供了一个简单的替代证明。其次，我们提出了一种随机算法，该算法将通行证复杂性降低到$ o（\ sqrt {n}）$，并且在通行证复杂性和空间用法之间也提供了平稳的权衡。
The semi-streaming model is a variant of the streaming model frequently used for the computation of graph problems. It allows the edges of an $n$-node input graph to be read sequentially in $p$ passes using $\tilde{O}(n)$ space. In this model, some graph problems, such as spanning trees and $k$-connectivity, can be exactly solved in a single pass; while other graph problems, such as triangle detection and unweighted all-pairs shortest paths, are known to require $\tildeΩ(n)$ passes to compute. For many fundamental graph problems, the tractability in these models is open. In this paper, we study the tractability of computing some standard spanning trees. Our results are: (1) Maximum-Leaf Spanning Trees. This problem is known to be APX-complete with inapproximability constant $ρ\in[245/244,2)$. By constructing an $\varepsilon$-MLST sparsifier, we show that for every constant $\varepsilon > 0$, MLST can be approximated in a single pass to within a factor of $1+\varepsilon$ w.h.p. (albeit in super-polynomial time for $\varepsilon \le ρ-1$ assuming $\mathrm{P} \ne \mathrm{NP}$). (2) BFS Trees. It is known that BFS trees require $ω(1)$ passes to compute, but the naïve approach needs $O(n)$ passes. We devise a new randomized algorithm that reduces the pass complexity to $O(\sqrt{n})$, and it offers a smooth tradeoff between pass complexity and space usage. (3) DFS Trees. The current best algorithm by Khan and Mehta {[}STACS 2019{]} takes $\tilde{O}(h)$ passes, where $h$ is the height of computed DFS trees. Our contribution is twofold. First, we provide a simple alternative proof of this result, via a new connection to sparse certificates for $k$-node-connectivity. Second, we present a randomized algorithm that reduces the pass complexity to $O(\sqrt{n})$, and it also offers a smooth tradeoff between pass complexity and space usage.
