@article { ,
title = {Parameterized Counting and Cayley Graph Expanders},
abstract = {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 [1]-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.},
doi = {10.1137/22m1479804},
eissn = {1095-7146},
issn = {0895-4801},
issue = {2},
journal = {SIAM Journal on Discrete Mathematics},
note = {EPrint Processing Status: Full text deposited in DRO},
pages = {405-486},
publicationstatus = {Published},
publisher = {Society for Industrial and Applied Mathematics},
url = {https://durham-repository.worktribe.com/output/1173068},
volume = {37},
year = {2023},
author = {Peyerimhoff, Norbert and Roth, Marc and Schmitt, Johannes and Stix, Jakob and Vdovina, Alina and Wellnitz, Philip}
}