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

preprint2014arXivOpen access

Abstract

For a class H\mathcal{H} of graphs, #Sub(H)(\mathcal{H}) is the counting problem that, given a graph H∈HH\in \mathcal{H} and an arbitrary graph GG, asks for the number of subgraphs of GG isomorphic to HH. It is known that if H\mathcal{H} has bounded vertex-cover number (equivalently, the size of the maximum matching in H\mathcal{H} is bounded), then #Sub(H)(\mathcal{H}) is polynomial-time solvable. We complement this result with a corresponding lower bound: if H\mathcal{H} is any recursively enumerable class of graphs with unbounded vertex-cover number, then #Sub(H)(\mathcal{H}) is #W[1]-hard parameterized by the size of HH 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 kk-matchings in bipartite graphs is #W[1]-hard. Recently, Curticapean [ICALP 2013] proved the #W[1]-hardness of counting kk-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)f(k)n^{o(k/\log k)} time algorithm for counting kk-matchings in bipartite graphs for any computable function f(k)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 kk is #W[1]-hard, as well as a similar almost-tight ETH-based lower bound on the exponent.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.