Lower Bounds for Induced Cycle Detection in Distributed Computing

François Le Gall, Masayuki Miyamoto

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 com…