Testing Cₖ-freeness in bounded-arboricity graphs

We study the problem of testing Cₖ-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ₖ with high constant probability when the graph is -far from Cₖ-free. We next state our results for constant arboricity and constant with a focus on the dependence on the number of graph vertices, n. The query complexity of all our algorithms grows polynomially with 1/. (1) As opposed to the case of k=3, where the complexity of testing C₃-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 (n^1/4) queries are necessary for testing C₄-freeness, and that O (n^1/4) are sufficient. The same bounds hold for C₅. (2) For every fixed k 6, any one-sided error algorithm for testing Cₖ-freeness must perform (n^1/3) queries. (3) For k=6 we give a testing algorithm whose query complexity is O (n^1/2). (4) For any fixed k, the query complexity of testing Cₖ-freeness is upper bounded by O (n^1-1/ k/2). Our (n^1/4) lower bound for testing C₄-freeness in constant arboricity graphs provides a negative answer to an open problem posed by (Goldreich, 2021).