2021/10/02 by Gall, François Le, Miyamoto, Masayuki
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2110.00741
The distributed subgraph detection asks, for a fixed graph H, whether the n-node input graph contains H as a subgraph or not. In the standard CONGEST model of distributed computing, the complexity of clique/cycle detection and listing has received a lot of attention recently. In this paper we consider the induced variant of subgraph detection, where the goal is to decide whether the n-node input graph contains H as an induced subgraph or not. We first show a Ω(n) lower bound for detecting the existence of an induced k-cycle for any k≥ 4 in the CONGEST model. This lower bound is tight for k=4, and shows that the induced variant of k-cycle detection is much harder than the non-induced version. This lower bound is proved via a reduction from two-party communication complexity. We complement this result by showing that for 5≤ k≤ 7, this Ω(n) lower bound cannot be improved via the two-party communication framework. We then show how to prove stronger lower bounds for larger values of k. More precisely, we show that detecting an induced k-cycle for any k≥ 8 requires Ω(n^2-Θ(1/k)) rounds in the CONGEST model, nearly matching the known upper bound O(n^2-Θ(1/k)) of the general k-node subgraph detection (which also applies to the induced version) by Eden, Fiat, Fischer, Kuhn, and Oshman~[DISC 2019]. Finally, we investigate the case where H is the diamond (the diamond is obtained by adding an edge to a 4-cycle, or equivalently removing an edge from a 4-clique), and show non-trivial upper and lower bounds on the complexity of the induced version of diamond detecting and listing.