2026-08-04T09:27:23Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20203 2024-07-02T07:52:51Z ddc:004 open_access

Testing C_k-Freeness in Bounded-Arboricity Graphs Eden, Talya Levi, Reut Ron, Dana Property Testing Cycle-Freeness Bounded Arboricity 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 ε-far from C_k-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 Õ(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_k-freeness must perform Ω(n^{1/3}) queries. 3) For k = 6 we give a testing algorithm whose query complexity is Õ(n^{1/2}). 4) For any fixed k, the query complexity of testing C_k-freeness is upper bounded by {O}(n^{1-1/⌊k/2⌋}). The last upper bound builds on another result in which we show that for any fixed subgraph F, the query complexity of testing F-freeness is upper bounded by O(n^{1-1/𝓁(F)}), where 𝓁(F) is a parameter of F that is always upper bounded by the number of vertices in F (and in particular is k/2 in C_k for even k). We extend some of our results to bounded (non-constant) arboricity, where in particular, we obtain sublinear upper bounds for all k. 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). Schloss Dagstuhl – Leibniz-Zentrum für Informatik Talya Eden and Reut Levi and Dana Ron 2024 Is Part Of LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2024.60 urn:nbn:de:0030-drops-202033 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.60 eng https://creativecommons.org/licenses/by/4.0/legalcode