论文标题
在动态图流中匹配和顶点盖的最佳下限
Optimal Lower Bounds for Matching and Vertex Cover in Dynamic Graph Streams
论文作者
论文摘要
在本文中，我们在近似最大匹配和带有删除的最小顶点盖的单向两党通信复杂性上提供了简单的最佳下限。在我们的模型中，爱丽丝拥有一组边缘，并向鲍勃发送了一条消息。鲍勃（Bob）拥有一组边缘删除，这些删除形成了爱丽丝（Alice）边缘的子集，并且需要在图表中报告大型匹配或小顶点盖，该盖子被未删除的边缘跨越。我们的结果暗示着插入局部流媒体算法的最佳空间下限，以实现最大匹配和最小顶点盖。 以前，Assadi等。 [SODA 2016]给出了插入局部流算法的最佳空间下限，以通过同时的通信模型进行最大匹配。我们的下限在几个方面越来越简单，更强壮：Assadi等人的下限。仅适用于（1）能够处理包含$ n $（输入图的顶点的数量）的删除数字的删除数的算法； （2）能够处理多画画； （3）在随机算法错误时，切勿在输入图中输出边缘。相比之下，我们的下限甚至适用于（1）依靠短（$ o（n^2）$ - 长度）输入流的算法； （2）只能处理简单的图； （3）当算法错误时可能会输出不存在的边缘。
In this paper, we give simple optimal lower bounds on the one-way two-party communication complexity of approximate Maximum Matching and Minimum Vertex Cover with deletions. In our model, Alice holds a set of edges and sends a single message to Bob. Bob holds a set of edge deletions, which form a subset of Alice's edges, and needs to report a large matching or a small vertex cover in the graph spanned by the edges that are not deleted. Our results imply optimal space lower bounds for insertion-deletion streaming algorithms for Maximum Matching and Minimum Vertex Cover. Previously, Assadi et al. [SODA 2016] gave an optimal space lower bound for insertion-deletion streaming algorithms for Maximum Matching via the simultaneous model of communication. Our lower bound is simpler and stronger in several aspects: The lower bound of Assadi et al. only holds for algorithms that (1) are able to process streams that contain a triple exponential number of deletions in $n$, the number of vertices of the input graph; (2) are able to process multi-graphs; and (3) never output edges that do not exist in the input graph when the randomized algorithm errs. In contrast, our lower bound even holds for algorithms that (1) rely on short ($O(n^2)$-length) input streams; (2) are only able to process simple graphs; and (3) may output non-existing edges when the algorithm errs.
