Counting Small Induced Subgraphs: Hardness via Fourier Analysis

For a fixed graph property Φ and integer k ≥ 1, the problem #IndSub(Φ,k) asks to count the induced k-vertex subgraphs satisfying Φ in an input graph G. If Φ is trivial on k-vertex graphs (i.e., if Φ contains either all or no k-vertex graphs), this problem is trivial. Otherwise we prove, among other results: - If Φ is edge-monotone (i.e., closed under deleting edges), then #IndSub(Φ,k) cannot be solved in time nᵒ⁽ᵏ⁾ assuming ETH. This strengthens a result by D\"oring, Marx and Wellnitz [STOC 2024] that only ruled out an exponent of o(√log k/ log log k). Our results also hold when counting modulo fixed primes. - If there is some fixed ε > 0 such that at most (2-ε)^k2 graphs on k vertices satisfy Φ, then #IndSub(Φ,k) cannot be solved in time no(k/√log k) assuming ETH. Our results hold even when each of the graphs in Φ may come with an arbitrary individual weight. This generalizes previous results for hereditary properties by Focke and Roth [SIAM J.\ Comput.\ 2024] up to a √log k factor in the exponent of the lower bound. - If Φ only depends on the number of edges, then #IndSub(Φ,k) cannot be solved in time nᵒ⁽ᵏ⁾ assuming ETH. This improves on a lower bound by Roth, Schmitt and Wellnitz [FOCS 2020] that only ruled out an exponent of o(k / √log k). In all cases, we also obtain #W[1]-hardness if k is part of the input and the problem is parameterized by k. We also obtain lower bounds on the Weisfeiler-Leman dimension. Our results follow from relatively straightforward Fourier analysis, and our paper subsumes most of the known #W[1]-hardness results known in the area, often with tighter lower bounds under ETH.