Count on CFI graphs for #P-hardness

A homomorphism between graphs H and G, possibly with vertex-colors, is a function f : V (H) → V (G) that preserves colors and edges. Many interesting graph parameters are finite linear combinations p(· ) = αH hom(H, · ) of homomorphism counts from fixed pattern graphs H; this includes (induced) subgraph counts for fixed patterns. Interpreting graph parameters as linear combinations of homomorphism counts has proven to be useful in understanding their computational complexity, as it is known that such linear combinations are as hard to evaluate as their hardest terms, whose complexity in turn is governed by the treewidth of the pattern graph. More formally, given oracle access to a linear combination of homomorphism counts p as above and a graph S with coefficient αS ≠ 0, it is possible to compute hom(S, G) for any nvertex input graph G in 2E(S)poly(s, n) time, where s is the maximum size of graphs in the defining linear combination of p. This reduction runs in polynomial time when p and S are fixed or small in comparison to G; this is the relevant setting in several results based on this reduction. In this paper, we show that a similar reduction can be performed in poly(n, s) time even if S is part of the input, provided that S has constant maximum degree. Our polynomial-time reduction is based on graph products with Cai-Fürer-Immerman graphs, a novel technique that is likely of independent interest in algorithms and complexity. The new reduction yields #P-hardness results for problems that could previously only be studied under parameterized complexity assumptions such as FPT ≠ #W[1], which are a priori stronger than classical assumptions. This includes the problems #Hom(H), #Sub(H) and #Ind(H) for fixed graph classes H satisfying natural polynomial-time enumerability conditions, which ask to count homomorphisms from H to G or (induced) subgraph copies of H in G, given as input a graph H ∈ H and a general graph G.