Counting Small Induced Subgraphs with Edge-Monotone Properties

We study the parameterized complexity of #IndSub(Φ), where given a graph 𝐺 and an integer 𝑘, the task is to count the number of induced subgraphs on 𝑘 vertices that satisfy the graph property Φ. Focke and Roth [STOC 2022] completely characterized the complexity for each Φ that is a hereditary property (that is, closed under vertex deletions): #IndSub(Φ) is #W[1]-hard except in the degenerate cases when every graph satisfies Φ or only finitely many graphs satisfy Φ. We complement this result with a classification for each Φ that is edge monotone (that is, closed under edge deletions): #IndSub(Φ) is #W[1]-hard except in the degenerate case when there are only finitely many integers 𝑘 such that Φ is nontrivial on 𝑘-vertex graphs. Our result generalizes earlier results for specific properties Φ 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(Φ) cannot be solved in time 𝑓 (𝑘) • |𝑉(𝐺)| 𝑜( √ log 𝑘/log log 𝑘) for any function 𝑓 , unless the Exponential-Time Hypothesis (ETH) fails. For many natural properties, we obtain even a tight bound 𝑓 (𝑘) • |𝑉(𝐺)| 𝑜( 𝑘) ; for example, this is the case for every property Φ that is nontrivial on 𝑘-vertex graphs for each 𝑘 greater than some 𝑘 0 .