Sublinear-time distributed algorithms for detecting small cliques and even cycles

In this paper we give sublinear-time distributed algorithms in the \(\mathsf {CONGEST}\) model for finding or listing cliques and even-length cycles. We show for the first time that all copies of 4-cliques and 5-cliques in the network graph can be detected and listed in sublinear time, \(O(n^{5/6+o(1)})\) rounds and \(O(n^{73/75+o(1)})\) rounds, respectively. For even-length cycles, \(C_{2k}\), we give an improved sublinear-time algorithm, which exploits a new connection to extremal combinatorics. For example, for 6-cycles we improve the running time from \({\tilde{O}}(n^{5/6})\) to \({\tilde{O}}(n^{3/4})\) rounds. We also show two obstacles on proving lower bounds for \(C_{2k}\)-freeness: first, we use the new connection to extremal combinatorics to show that the current lower bound of \({\tilde{\varOmega }}(\sqrt{n})\) rounds for 6-cycle freeness cannot be improved using partition-based reductions from 2-party communication complexity, the technique by which all known lower bounds on subgraph detection have been proven to date. Second, we show that there is some fixed constant \(\delta \in (0,1/2)\) such that for any k, a lower bound of \(\varOmega (n^{1/2+\delta })\) on \(C_{2k}\)-freeness would imply new lower bounds in circuit complexity. We use the same technique to show a barrier for proving any polynomial lower bound on triangle-freeness. For general subgraphs, it was shown by Fischer et al. that for any fixed k, there exists a subgraph H of size k such that H-freeness requires \({\tilde{\varOmega }}(n^{2-\varTheta (1/k)})\) rounds. It was left as an open problem whether this is tight, or whether some constant-sized subgraph requires truly quadratic time to detect. We show that in fact, for any subgraph H of constant size k, the H-freeness problem can be solved in \(O(n^{2 - \varTheta (1/k)})\) rounds, nearly matching the lower bound.