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 Ω(n1/4) queries are necessary for testing C₄-freeness, and that O(n1/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 Ω(n1/3) queries. (3) For $k=6$ we give a testing algorithm whose query complexity is O(n1/2). (4) For any fixed k, the query complexity of testing Cₖ-freeness is upper bounded by O(n1-1/ k/2). Our Ω(n1/4) lower bound for testing C₄-freeness in constant arboricity graphs provides a negative answer to an open problem posed by (Goldreich, 2021).