Paper Info
Title
Faster Algorithms For Counting Subgraphs In Sparse Graphs
Abstract
Given a k-node pattern graph H and an n-node host graph G, the subgraph counting problem asks to compute the number of copies of H in G. In this work we address the following question: can we count the copies of H faster if G is sparse? We answer in the affirmative by introducing a novel tree-like decomposition for directed acyclic graphs, inspired by the classic tree decomposition for undirected graphs. This decomposition gives a dynamic program for counting the homomorphisms of H in G by exploiting the degeneracy of G, which allows us to beat the state-of-theart subgraph counting algorithms when G is sparse enough. For example, we can count the induced copies of any k-node pattern H in time 2(O(k2)) O(n(0.25k+2) log n) if G has bounded degeneracy, and in time 2(O(k2))O(n(0.625k+2) log n) if G has bounded average degree. These bounds are instantiations of a more general result, parameterized by the degeneracy of G and the structure of H, which generalizes classic bounds on counting cliques and complete bipartite graphs. We also give lower bounds based on the Exponential Time Hypothesis, showing that our results are actually a characterization of the complexity of subgraph counting in bounded-degeneracy graphs.
Year
DOI
Venue
2021
10.1007/s00453-021-00811-0
ALGORITHMICA
Keywords
DocType
Volume
Subgraph counting, Tree decomposition, Degeneracy, Sparsity
Journal
83
Issue
ISSN
Citations 
8
0178-4617
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Marco Bressan100.34