Skip to main content

Research Repository

Advanced Search

Parameterized Counting and Cayley Graph Expanders

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

Parameterized Counting and Cayley Graph Expanders Thumbnail


Marc Roth

Johannes Schmitt

Jakob Stix

Alina Vdovina

Philip Wellnitz


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.


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.

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
Public URL


Published Journal Article (4.2 Mb)

Copyright Statement
© 2023 Society for Industrial and Applied Mathematics.

You might also like

Downloadable Citations