2026-07-22T15:45:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22874 2025-10-09T07:19:56Z ddc:004 open_access

Cycle Counting Under Local Differential Privacy for Degeneracy-Bounded Graphs Hillebrand, Quentin Suppakitpaisarn, Vorapong Shibuya, Tetsuo Differential privacy triangle counting degeneracy arboricity graph theory parameterized accuracy We propose an algorithm for counting the number of cycles under local differential privacy for degeneracy-bounded input graphs. Numerous studies have focused on counting the number of triangles under the privacy notion, demonstrating that the expected 𝓁₂-error of these algorithms is Ω(n^{1.5}), where n is the number of nodes in the graph. When parameterized by the number of cycles of length four (C₄), the best existing triangle counting algorithm has an error of O(n^{1.5} + √C₄) = O(n²). In this paper, we introduce an algorithm with an expected 𝓁₂-error of O(δ^1.5 n^0.5 + δ^0.5 d_max^0.5 n^0.5), where δ is the degeneracy and d_{max} is the maximum degree of the graph. For degeneracy-bounded graphs (δ ∈ Θ(1)) commonly found in practical social networks, our algorithm achieves an expected 𝓁₂-error of O(d_{max}^{0.5} n^{0.5}) = O(n). Our algorithm’s core idea is a precise count of triangles following a preprocessing step that approximately sorts the degree of all nodes. This approach can be extended to approximate the number of cycles of length k, maintaining a similar 𝓁₂-error, namely O(δ^{(k-2)/2} d_max^0.5 n^{(k-2)/2} + δ^{k/2} n^{(k-2)/2}) or O(d_max^0.5 n^{(k-2)/2}) = O(n^{(k-1)/2}) for degeneracy-bounded graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Quentin Hillebrand and Vorapong Suppakitpaisarn and Tetsuo Shibuya 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.49 urn:nbn:de:0030-drops-228748 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.49 eng https://creativecommons.org/licenses/by/4.0/legalcode