Possibilities and Impossibilities for Distributed Subgraph Detection
Possibilities and Impossibilities for Distributed Subgraph Detection
复制标题
分布式子图检测的可能性和不可能性
DOI：
--
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
R. Oshman
中科院分区：
文献类型：
--
作者：
O. Fischer;T. Gonen;F. Kuhn;R. Oshman
在分布式子图检测问题中，给定一个固定的子图H，网络必须判断该网络图中是否包含H的副本。如果消息大小无界，子图检测可以在恒定的轮数内解决，但在CONGEST模型中，每个消息的大小都有界，它可能具有很高的轮复杂度。分布式子图检测近年来受到了广泛关注，提出了新的上下界，但仍有几个基本问题有待解决。在本文中，我们证明了在CONGEST模型中子图检测的新的可能性和不可能性结果。我们首次展示了一些子图需要超线性——事实上，接近二次的——运行时间，即使在小直径的网络中也是如此。我们还研究了周期检测，并表明任何偶数周期都可以在亚线性时间内检测到（而奇周期则需要线性时间）。对于三角形检测的特殊情况，我们表明确定性算法即使在度为2的图中也需要$Ømega（łog n）$总通信，并且一轮随机算法必须在度为Δ的图中发送$Ømega（Δ）$位，改进了[Abboud等人]最近的结果。最后，我们将最近的[Izumi， Le Gall]的下界推广到列出所有三角形的任意大小的集团。
In the distributed subgraph detection problem, we are given a fixed subgraph H , and the network must decide whether the network graph contains a copy of H or not. Subgraph detection can be solved in a constant number of rounds if message size is unbounded, but in the CONGEST model, where each message has bounded size, it can have high round complexity. Distributed subgraph detection has received significant attention recently, with new upper and lower bounds, but several fundamental questions remain open. In this paper we prove new possibility and impossibility results for subgraph detection in the CONGEST model. We show for the first time that some subgraphs require superlinear --- in fact, nearly quadratic --- running time, even in small-diameter networks. We also study cycle-detection, and show that any even cycle can be detected in sublinear time (in contrast to odd cycles, which require linear time). For the special case of triangle-detection, we show that deterministic algorithms require $Ømega(łog n)$ total communication even in graphs of degree 2, and that one-round randomized algorithms must send $Ømega(Δ)$ bits in graphs of degree Δ, improving on the recent results of [Abboud et. al.]. Finally, we extend a recent lower bound of [Izumi, Le Gall] on listing all triangles to cliques of any size.