Testing $C_k$-freeness in bounded-arboricity graphs

Abstract

We study the problem of testing $C_k$-freeness ($k$-cycle-freeness) for fixed constant $k>3$ in graphs with bounded arboricity (but unbounded degrees). In particular, we are interested in one-sided error algorithms, so that they must detect a copy of $C_k$ with high constant probability when the graph is $\hat{I}\mu$-far from $C_k$-free. We next state our results for constant arboricity and constant $\hat{I}\mu$ with a focus on the dependence on the number of graph vertices, $n$. The query complexity of all our algorithms grows polynomially with $1/\hat{I}\mu$. (1) As opposed to the case of $k=3$, where the complexity of testing $C_3$-freeness grows with the arboricity of the graph but not with the size of the graph (Levi, ICALP 2021) this is no longer the case already for $k=4$. We show that $\hat{I}\text{c◯}(n^{1/4})$ queries are necessary for testing $C_4$-freeness, and that $\tilde{O}(n^{1/4})$ are sufficient. The same bounds hold for $C_5$. (2) For every fixed $k\ge 6$, any one-sided error algorithm for testing $C_k$-freeness must perform $\hat{I}\text{c◯}(n^{1/3})$ queries. (3) For $k=6$ we give a testing algorithm whose query complexity is $\tilde{O}(n^{1/2})$. (4) For any fixed $k$, the query complexity of testing $C_k$-freeness is upper bounded by $O(n^{1-1/\lfloor k/2\rfloor })$. Our $\hat{I}\text{c◯}(n^{1/4})$ lower bound for testing $C_4$-freeness in constant arboricity graphs provides a negative answer to an open problem posed by (Goldreich, 2021).