The \(\mathsf {CONGEST}\)  model:
For 4-cycle detection, Drucker, Kuhn, and Oshman [1]} provide a tight complexity of \(\tilde{\Theta }(n^{1/2})\) , by providing both an algorithm and a lower bound. They also show that for any odd value of \(p\) , detecting \(p\) -cycles requires \(\tilde{\Omega }(n)\)  rounds. The upper bound is obtained by setting a threshold of \(T=2n^{1/2}\) , and defining heavy nodes as nodes with at least \(T\)  neighbors. First, all non-heavy nodes send all their neighbors to all their neighbors, in \(T\)  rounds. This detects 4-cycles which have at least 2 non-neighboring non-heavy nodes. Then, a heavy node \(v\)  with more than \(T\)  heavy neighbors reports that there exists a 4-cycle. Finally, a heavy node \(v\)  with at most \(T\)  heavy neighbors sends its heavy neighbors to all of its neighbors, again in \(T\)  rounds. The reason for which too many heavy neighbors imply a 4-cycle is because this means that the total number of neighbors of heavy neighbors is at least \(T^2\) , which is more than \(2n\) , and so there must be a node other than \(v\)  which is connected to two of the neighbors of \(v\) , and hence we have a 4-cycle. Otherwise, if \(v\)  sends its heavy neighbors to all of its neighbors, then any 4-cycle with two neighboring nodes that are heavy is detected by one of its nodes (by a simple case analysis).
