This paper addresses an open problem I posed in HERE. Specifically, I asked whether it is possible to transform (with small overhead) property testers for bounded degree graphs to property testers for unbounded degree graphs with bounded arboricity. The new result for the natural problem of testing $C_4$-freeness should be viewed as a negative answer (at least for the one-sided error case).
The specific results are clearly stated in the abstract.
We study the problem of testing Ck-freeness (k-cycle-freeness) for fixed constant $k geq 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 Ck with high constant probability when the graph is espilon-far from Ck-free. We next state our results for constant arboricity and constant epsilon with a focus on the dependence on the number of graph vertices, n. The query complexity of all our algorithms grows polynomially with 1/epsilon.
Our Omega(n^{1/4}) lower bound for testing C4-freeness in constant arboricity graphs provides a negative answer to an open problem posed by (Goldreich, 2021).