非表示:
キーワード:
Computer Science, Computational Complexity, Discrete Mathematics
要旨:
We study the problem $\#\mathrm{EdgeSub}(\Phi)$ 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
$\#\mathrm{EdgeSub}(\Phi)$ 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$.
