2026-07-23T22:06:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:23501 2025-10-02T12:57:00Z ddc:004 open_access

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs Paul-Pena, Daniel Seshadhri, C. Homomorphism counting Bounded degeneracy graphs Fine-grained complexity Subgraph counting We study the classic problem of subgraph counting, where we wish to determine the number of occurrences of a fixed pattern graph H in an input graph G of n vertices. Our focus is on bounded degeneracy inputs, a rich family of graph classes that also characterizes real-world massive networks. Building on the seminal techniques introduced by Chiba-Nishizeki (SICOMP 1985), a recent line of work has built subgraph counting algorithms for bounded degeneracy graphs. Assuming fine-grained complexity conjectures, there is a complete characterization of patterns H for which linear time subgraph counting is possible. For every r ≥ 6, there exists an H with r vertices that cannot be counted in linear time. In this paper, we initiate a study of subquadratic algorithms for subgraph counting on bounded degeneracy graphs. We prove that when H has at most 9 vertices, subgraph counting can be done in Õ(n^{5/3}) time. As a secondary result, we give improved algorithms for counting cycles of length at most 10. Previously, no subquadratic algorithms were known for the above problems on bounded degeneracy graphs. Our main conceptual contribution is a framework that reduces subgraph counting in bounded degeneracy graphs to counting smaller hypergraphs in arbitrary graphs. We believe that our results will help build a general theory of subgraph counting for bounded degeneracy graphs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Paul-Pena and C. Seshadhri 2025 Is Part Of LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2025.124 urn:nbn:de:0030-drops-235010 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.124 eng https://creativecommons.org/licenses/by/4.0/legalcode