Abstract
For a class of graphs, #Sub is the counting problem that, given a graph and an arbitrary graph , asks for the number of subgraphs of isomorphic to . It is known that if has bounded vertex-cover number (equivalently, the size of the maximum matching in is bounded), then #Sub is polynomial-time solvable. We complement this result with a corresponding lower bound: if is any recursively enumerable class of graphs with unbounded vertex-cover number, then #Sub is #W[1]-hard parameterized by the size of 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 -matchings in bipartite graphs is #W[1]-hard. Recently, Curticapean [ICALP 2013] proved the #W[1]-hardness of counting -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 time algorithm for counting -matchings in bipartite graphs for any computable function . 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 is #W[1]-hard, as well as a similar almost-tight ETH-based lower bound on the exponent.
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.