Parameterized (Modular) Counting and Cayley Graph Expanders

DOI10.4230/LIPICS.MFCS.2021.84MaRDI QIDQ6113372zbMATH OpenOpenAlexFDO

Authors Norbert Peyerimhoff, Marc Roth, Johannes Schmitt, Jakob Stix, Alina Vdovina

Publication date 8 August 2023

Full work available at URL https://arxiv.org/abs/2104.14596

zbMATH Keywords

Cayley graphscounting complexityexpander graphsfine-grained complexityparameterized complexity

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We study the problem $$ of counting $k$-edge subgraphs satisfying a given graph property $Phi$ 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 $$ for minor-closed properties $Phi$, 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$.

Recommendations

• Counting Subgraphs via Homomorphisms
• Counting homomorphisms modulo a prime number
• Homomorphisms are a good basis for counting small subgraphs
• Counting homomorphisms to trees modulo a prime
• Counting homomorphisms to trees modulo a prime

Cited in

(4)

• Parameterised counting in logspace
• Parameterised and fine-grained subgraph counting, modulo 2
• Parameterized Counting and Cayley Graph Expanders
• Parameterised holant problems

This page was built for publication: Parameterized (Modular) Counting and Cayley Graph Expanders

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6113372)