Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness

Marc Roth, Johannes Schmitt

We investigate the problem $\#\mathsf{IndSub}(\Phi )$ of counting all induced subgraphs of size $k$ in a graph $G$ that satisfy a given property $\Phi$. This continues the work of Jerrum…