2021/03/09 by Marco Bressan, Bressan, Marco, Marc Roth +1 · 3 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2103.05588
openalex publication_date 2021/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study the problems of counting the homomorphisms, counting the copies, and counting the induced copies of a k-vertex graph H in a d-degenerate n-vertex graph G. Our main result establishes exhaustive and explicit complexity classifications for counting subgraphs and induced subgraphs. We show that the (not necessarily induced) copies of H in G can be counted in time f(k,d)⋅ nmax(imn(H),1)⋅ log n, where f is some computable function and imn(H) is the size of the largest induced matching of H. Whenever the class of allowed patterns has unbounded induced matching number, this algorithm is essentially optimal: Unless the Exponential Time Hypothesis (ETH) fails, there is no algorithm running in time f(k,d)⋅ no(imn(H)/log imn(H)) for any function f. In case of counting induced subgraphs, we obtain a similar classification along the independence number α: we can count the induced copies of H in G in time f(k,d)⋅ nα(H)⋅ log n, and if the class of allowed patterns has unbounded independence number, an algorithm running in time f(k,d)⋅ no(α(H)/log α(H)) is impossible, unless ETH fails. In the language of parameterized complexity, our results yield dichotomies in fixed-parameter tractable and #W[1]-hard cases if we parameterize by the size of the pattern and the degeneracy of the host graph. Our results imply that several patterns cannot be counted in time f(k,d)⋅ no(k/log k), including k-matchings, k-independent sets, (induced) k-paths, (induced) k-cycles, and induced (k,k)-bicliques, unless ETH fails. Those lower bounds for exact counting are complemented with new algorithms for approximate counting of subgraphs and induced subgraphs in degenerate graphs.