Abstract. Given a graph property [Formula: see text], we consider the problem [Formula: see text] EdgeSub [Formula: see text], where the input is a pair of a graph [Formula: see text] and a positive integer [Formula: see text], and the task is to compute the number of [Formula: see text]-edge subgraphs in [Formula: see text] that satisfy [Formula: see text]. Specifically, we study the parameterized complexity of [Formula: see text] EdgeSub [Formula: see text] with respect to both approximate and exact counting, as well as its decision version EdgeSub [Formula: see text]. Among others, our main result fully resolves the case of minor-closed properties [Formula: see text]: the decision problem EdgeSub [Formula: see text] always admits a fixed-parameter tractable algorithm, and the counting problem [Formula: see text] EdgeSub [Formula: see text] always admits a fixed-parameter tractable randomized approximation scheme. For exact counting, we present an exhaustive and explicit criterion on the property [Formula: see text] which, if satisfied, yields fixed-parameter tractability and otherwise [Formula: see text]-hardness. Additionally, our hardness results come with an almost tight conditional lower bound under the exponential time hypothesis. Our main technical result concerns the exact counting problem: Building upon the breakthrough result of Curticapean, Dell, and Marx (Symposium on Theory of Computing 2017), we express the number of subgraphs satisfying [Formula: see text] as a finite linear combination of graph homomorphism counts and derive the complexity of computing this number by studying its coefficients. Our approach relies on novel constructions of low-degree Cayley graph expanders of [Formula: see text]-groups, which might be of independent interest. The properties of those expanders allow us to analyze the coefficients in the aforementioned linear combinations over the field [Formula: see text] which gives us significantly more control over the cancelation behavior of the coefficients.

We study the problem $\#\mathrm{EdgeSub}(Φ)$ of counting $k$-edge subgraphs satisfying a given graph property $Φ$ in a large host graph $G$. Building upon the breakthrough result of Curticapean, Dell and Marx (STOC 17), we express the number of such subgraphs as a finite linear combination of graph homomorphism counts and derive the complexity of computing this number by studying its coefficients. Our approach relies on novel constructions of low-degree Cayley graph expanders of $p$-groups, which might be of independent interest. The properties of those expanders allow us to analyse the coefficients in the aforementioned linear combinations over the field $\mathbb{F}_p$ which gives us significantly more control over the cancellation behaviour of the coefficients. Our main result is an exhaustive and fine-grained complexity classification of $\#\mathrm{EdgeSub}(Φ)$ for minor-closed properties $Φ$, closing the missing gap in previous work by Roth, Schmitt and Wellnitz (ICALP 21). Additionally, we observe that our methods also apply to modular counting. Among others, we investigate the problems of modular counting of paths, cycles, forests and matroid bases. In the course of our investigations we also provide an exhaustive parameterized complexity classification for the problem of counting graph homomorphisms modulo a prime $p$.