Detecting graphs with induced cycles in limited-bandwidth communication networks
The subgraph detection problem is a fundamental problem in distributed algorithms that asks the nodes of a communication network G to determine if that communication network contains a specific graph P as a subgraph. Recent work in this area has largely been focused on the case where the nodes have limited bandwidth and thus cannot communicate arbitrarily, which is part of a larger movement in distributed algorithms to reduce the amount of communication that our algorithms require. We show that, if P is a graph containing an induced cycle of length at least 4, then detecting a rainbow copy of P (in terms of vertex colourings or edge colourings) takes at least Ω(n/ log n) in the CONGEST model. Motivated by this result, we go on to show that, if P is a necklace graph containing an odd cycle of length at least 5, then detecting a copy of P takes at least Ω(n/ log n) rounds in the CONGEST model. Finally, we discuss techniques for proving similar results when P is a necklace graph containing all even cycles or a 3-cycle, and highlight the difficulties in doing so.
CONGEST, Subgraph detection, Distributed computing, Induced subgraphs, Limited-bandwidth communication networks, Lower bounds