LAUSR

We study the problem $$\#\textsc {IndSub}(\varPhi )$$ # I N D S U B ( Φ ) of counting all induced subgraphs of size k in a graph G that satisfy the property $$\varPhi $$ Φ . It is shown that, given any graph property $$\varPhi $$ Φ that distinguishes independent sets from bicliques, $$\#\textsc {IndSub}(\varPhi )$$ # I N D S U B ( Φ ) is hard for the class $$\#\mathsf {W[1]}$$ # W [ 1 ] , i.e., the parameterized counting equivalent of $${{\mathsf {N}}}{{\mathsf {P}}}$$ N P . Under additional suitable density conditions on $$\varPhi $$ Φ , satisfied e.g. by non-trivial monotone properties on bipartite graphs, we strengthen $$\#\mathsf {W[1]}$$ # W [ 1 ] -hardness by establishing that $$\#\textsc {IndSub}(\varPhi )$$ # I N D S U B ( Φ ) cannot be solved in time $$f(k)\cdot n^{o(k)}$$ f ( k ) · n o ( k ) for any computable function f, unless the Exponential Time Hypothesis fails. Finally, we observe that our results remain true even if the input graph G is restricted to be bipartite and counting is done modulo a fixed prime.