Testing Ck-freeness in bounded-arboricity graphs

Oded's comments

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.

The original 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.

1. As opposed to the case of k=3, where the complexity of testing C3-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 Omega(n^{1/4}) queries are necessary for testing C4-freeness, and that tildeO(n^{1/4}) are sufficient. The same bounds hold for C5.
2. For every fixed $k geq 6$, any one-sided error algorithm for testing Ck-freeness must perform Omega(n^{1/3}) queries.
3. For k=6 we give a testing algorithm whose query complexity is tileeO(n^{1/2}).
4. For any fixed k, the query complexity of testing Ck-freeness is upper bounded by O(n^{1-(1/floor(k/2))}).

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).

See arXiv:2404.18126 [cs.DS].