Count on CFI graphs for #P-hardness
Count on CFI graphs for #P-hardness
A homomorphism between graphs H and G, possibly with vertex-colors, is a function f : V(ℋ) → V(G) that preserves colors and edges. Many interesting graph parameters are finite linear combinations p(·) = Ση αH hom(ℋ, ·) of homomorphism counts from fixed pattern graphs H; this includes (induced) subgraph counts …