Lower Bounds for Induced Cycle Detection in Distributed Computing
share
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 Õ(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.
READ FULL TEXT