论文标题
两次通行图流算法的接近二次下限
Near-Quadratic Lower Bounds for Two-Pass Graph Streaming Algorithms
论文作者
论文摘要
我们证明，$ n $ vertex有向图中的$ s $ - $ t $可及性问题的任何两通道图流算法都需要$ n^{2-o（1）} $ bits的接近二次空间。作为推论，我们还获得了其他几个基本问题，包括最大的两分匹配和（大约）最短的路径，在无向图中，我们还获得了接近二次的空间下限。 我们的结果总体表明，即使允许两次通过输入，大量的图形问题基本上也没有非平凡的流媒体算法。在我们的工作之前，这种不可能的结果仅是单频道流算法而闻名的，而最佳的两次通行下限仅排除了$ O（n^{7/6}）$太空算法，在（琐碎）上限和下限之间留下了很大的差距。
We prove that any two-pass graph streaming algorithm for the $s$-$t$ reachability problem in $n$-vertex directed graphs requires near-quadratic space of $n^{2-o(1)}$ bits. As a corollary, we also obtain near-quadratic space lower bounds for several other fundamental problems including maximum bipartite matching and (approximate) shortest path in undirected graphs. Our results collectively imply that a wide range of graph problems admit essentially no non-trivial streaming algorithm even when two passes over the input is allowed. Prior to our work, such impossibility results were only known for single-pass streaming algorithms, and the best two-pass lower bounds only ruled out $o(n^{7/6})$ space algorithms, leaving open a large gap between (trivial) upper bounds and lower bounds.
