Given a graph property \Phi , we consider the problem \# EdgeSub(\Phi ), where the input is a pair of a graph G and a positive integer k, and the task is to compute the number of k-edge subgraphs in G that satisfy \Phi . Specifically, we study the parameterized complexity of \#EdgeSub(\Phi ) with respect to both approximate and exact counting, as well as its decision version EdgeSub(\Phi ). Among others, our main result fully resolves the case of minor-closed properties \Phi : the decision problem EdgeSub(\Phi ) always admits a fixed-parameter tractable algorithm, and the counting problem \#EdgeSub(\Phi ) always admits a fixed-parameter tractable randomized approximation scheme. For exact counting, we present an exhaustive and explicit criterion on the property \Phi which, if satisfied, yields fixed-parameter tractability and otherwise \#\sansW -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 \Phi 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 analyze the coefficients in the aforementioned linear combinations over the field \BbbF p which gives us significantly more control over the cancelation behavior of the coefficients.
Peyerimhoff, N., Roth, M., Schmitt, J., Stix, J., Vdovina, A., & Wellnitz, P. (2023). Parameterized Counting and Cayley Graph Expanders. SIAM Journal on Discrete Mathematics, 37(2), 405-486. https://doi.org/10.1137/22m1479804