Parameterized Counting and Cayley Graph Expanders

Peyerimhoff, Norbert; Roth, Marc; Schmitt, Johannes; Stix, Jakob; Vdovina, Alina; Wellnitz, Philip

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.

Citation

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

• Journal Article Type: Article
• Acceptance Date: Sep 13, 2022
• Online Publication Date: Apr 16, 2023
• Publication Date: 2023-06
• Deposit Date: Jun 7, 2023
• Publicly Available Date: Jun 7, 2023
• Journal: SIAM Journal on Discrete Mathematics
• Print ISSN: 0895-4801
• Electronic ISSN: 1095-7146
• Publisher: Society for Industrial and Applied Mathematics
• Peer Reviewed: Peer Reviewed
• Volume: 37
• Issue: 2
• Pages: 405-486
• DOI: https://doi.org/10.1137/22m1479804
• Public URL: https://durham-repository.worktribe.com/output/1173068