Counting Small Induced Subgraphs with Edge-monotone Properties

Abstract

We study the parameterized complexity of #IndSub($\Phi$), where given a graph $G$ and an integer $k$, the task is to count the number of induced subgraphs on $k$ vertices that satisfy the graph property $\Phi$. Focke and Roth [STOC 2022] completely characterized the complexity for each $\Phi$ that is a hereditary property (that is, closed under vertex deletions): #IndSub($\Phi$) is #W[1]-hard except in the degenerate cases when every graph satisfies $\Phi$ or only finitely many graphs satisfy $\Phi$. We complement this result with a classification for each $\Phi$ that is edge monotone (that is, closed under edge deletions): #IndSub($\Phi$) is #W[1]-hard except in the degenerate case when there are only finitely many integers $k$ such that $\Phi$ is nontrivial on $k$-vertex graphs. Our result generalizes earlier results for specific properties $\Phi$ that are related to the connectivity or density of the graph. Further, we extend the #W[1]-hardness result by a lower bound which shows that #IndSub($\Phi$) cannot be solved in time $f(k)\cdot |V(G){|}^{o(\sqrt{\log k/\log \log k})}$ for any function $f$, unless the Exponential-Time Hypothesis (ETH) fails. For many natural properties, we obtain even a tight bound $f(k)\cdot |V(G){|}^{o(k)}$; for example, this is the case for every property $\Phi$ that is nontrivial on $k$-vertex graphs for each $k$ greater than some $k_0$.