Counting Small Induced Subgraphs: Hardness via Fourier Analysis

For a fixed graph property $Φ$ and integer $k \geq 1$, consider the problem of counting the induced $k$-vertex subgraphs satisfying $Φ$ in an input graph $G$. This problem can be solved by brute-force in time $O(n^{k})$. Under ETH, we prove several lower bounds on the optimal exponent in this running time: If $Φ$ is edge-monotone (i.e., closed under deleting edges), then ETH rules out $n^{o(k)}$ time algorithms for this problem. This strengthens a recent lower bound by Döring, Marx and Wellnitz [STOC 2024]. Our result also holds for counting modulo fixed primes. If at most $(2-\varepsilon)^{\binom{k}{2}}$ graphs on $k$ vertices satisfy $Φ$, for some $\varepsilon > 0$, then ETH also rules out an exponent of $o(k)$. This holds even when the graphs in $Φ$ have arbitrary individual weights, generalizing previous results for hereditary properties by Focke and Roth [SIAM J. Comput. 2024]. If $Φ$ is non-trivial and excludes $β_Φ$ edge-densities, then the optimal exponent under ETH is $Ω(β_Φ)$. This holds even when the graphs in $Φ$ have arbitrary individual weights, generalizing previous results by Roth, Schmitt and Wellnitz [SIAM J. Comput. 2024]. In all cases, we also obtain $\mathsf{\#W[1]}$-hardness if $k$ is part of the input and considered as the parameter. We also obtain lower bounds on the Weisfeiler-Leman dimension. As opposed to the nontrivial techniques from combinatorics, group theory, and simplicial topology used before, our results follow from a relatively straightforward ``algebraization'' of the problem in terms of polynomials, combined with applications of simple algebraic facts, which can also be interpreted in terms of Fourier analysis.