Dichotomies for Counting Subgraphs
summary
Classifies when counting copies of H in G is fixed-parameter tractable: if the class C has bounded matching size (equivalently bounded vertex-cover) the problem is FPT/polynomial-time by brute-forcing the small vertex cover; if C admits arbitrarily large matchings the problem is #W[1]-hard. Proof uses excluded-grid/treewidth machinery to get hardness via grid minors, an FPT reduction from counting k-matchings (exploding vertices creates at most 3^k instances), inclusion–exclusion, and Ramsey-type arguments for induced matchings.
AI-written summary · about