# Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts

arXiv: https://arxiv.org/abs/1407.2929 · HTML: https://mlsanity.com/paper/1407.2929/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jul 2014.

## Built on by (most cited first, 1 of 1)

- [Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes](https://mlsanity.com/paper/2111.14148/) (2021)

## Abstract (arXiv)

For a class H of graphs, #Sub(H) is the counting problem that, given a graph H∈ H and an arbitrary graph G, asks for the number of subgraphs of G isomorphic to H. It is known that if H has bounded vertex-cover number (equivalently, the size of the maximum matching in H is bounded), then #Sub(H) is polynomial-time solvable. We complement this result with a corresponding lower bound: if H is any recursively enumerable class of graphs with unbounded vertex-cover number, then #Sub(H) is #W[1]-hard parameterized by the size of H and hence not polynomial-time solvable and not even fixed-parameter tractable, unless FPT = #W[1]. As a first step of the proof, we show that counting k-matchings in bipartite graphs is #W[1]-hard. Recently, Curticapean [ICALP 2013] proved the #W[1]-hardness of counting k-matchings in general graphs; our result strengthens this statement to bipartite graphs with a considerably simpler proof and even shows that, assuming the Exponential Time Hypothesis (ETH), there is no f(k)no(k/log k) time algorithm for counting k-matchings in bipartite graphs for any computable function f(k). As a consequence, we obtain an independent and somewhat simpler proof of the classical result of Flum and Grohe [SICOMP 2004] stating that counting paths of length k is #W[1]-hard, as well as a similar almost-tight ETH-based lower bound on the exponent.