论文标题
图形问题的空间下限
Space Lower Bounds for Graph Stream Problems
论文作者
论文摘要
这项工作涉及流媒体模型中图形问题的空间较低界限。众所周知，计算流模型中两个节点之间的最短路径长度需要$ω（n）$空间，其中$ n $是图中的节点数量。我们研究了在流模型中找到给定节点深度的问题。对于此问题，我们证明了一个紧密的单个通行空间下限和多通空间下限。由于这是计算图表上最短路径的特殊情况，因此上述下限也适用于流模型中的最短路径问题。结果是通过使用已知的通信复杂性下限或通过为问题构建硬实例而获得的。此外，我们将用于证明上述下限结果的技术应用于其他图形问题，以证明空间下限（单个和多量），例如查找Min $ s-t $ cut，检测负重周期，并发现两个节点是否位于相同的紧密连接的组件中。
This work concerns with proving space lower bounds for graph problems in the streaming model. It is known that computing the length of shortest path between two nodes in the streaming model requires $Ω(n)$ space, where $n$ is the number of nodes in the graph. We study the problem of finding the depth of a given node in a rooted tree in the streaming model. For this problem we prove a tight single pass space lower bound and a multipass space lower bound. As this is a special case of computing shortest paths on graphs, the above lower bounds also apply to the shortest path problem in the streaming model. The results are obtained by using known communication complexity lower bounds or by constructing hard instances for the problem. Additionally, we apply the techniques used in proving the above lower bound results to prove space lower bounds (single and multipass) for other graph problems like finding min $s-t$ cut, detecting negative weight cycle and finding whether two nodes lie in the same strongly connected component.
