Counting Induced Subgraphs: An Algebraic Approach to #W[1]-Hardness

We study the problem #INDSuB(Phi) of counting all induced subgraphs of size k in a graph G that satisfy the property Phi. It is shown that, given any graph property Phi that distinguishes independent sets from bicliques, #INDSuB(Phi) is hard for the class #W[1], i.e., the parameterized counting equivalent of NP. Under additional suitable density conditions on (1), satisfied e.g. by non-trivial monotone properties on bipartite graphs, we strengthen #W[1]-hardness by establishing that #INDSuB(Phi) cannot be solved in time f(k) . n degrees((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.