Counting Small Induced Subgraphs: Hardness via Fourier Analysis

For a fixed graph property Φ and integer k ≥ 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 -ε) ( k 2 ) graphs on k vertices satisfy Φ, for some ε > 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 #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. Most of the #W[1]-hardness results known in the area are subsumed by our paper, and our hardness results often hold in a more general setting.