Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866929739977981952 |
|---|---|
| author | Paul-Pena, Daniel Seshadhri, C. |
| author_facet | Paul-Pena, Daniel Seshadhri, C. |
| contents | 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 \geq 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 $\tilde{O}(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_08376 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs Paul-Pena, Daniel Seshadhri, C. Data Structures and Algorithms Discrete Mathematics 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 \geq 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 $\tilde{O}(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. |
| title | Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2410.08376 |