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 (nk ). 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 no(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 graphs on k vertices satisfy Φ, for some ε > 0, then ETH rules out an exponent of . 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] up to a factor in the exponent.

If Φ only depends on the number of edges, then the optimal exponent under ETH is Ω(k ). This improves on an lower bound by Roth, Schmitt and Wellnitz [FOCS 2020].

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.

Our results follow from relatively straightforward Fourier analysis, as opposed to the nontrivial techniques from combinatorics, group theory, and simplicial topology used in previous papers. Our paper subsumes most of the known #W[1]-hardness results known in the area, often with tighter lower bounds under ETH.