Count on CFI graphs for #P-hardness
share
Given graphs H and G, possibly with vertex-colors, a homomorphism is a function f:V(H)→ V(G) that preserves colors and edges. Many interesting counting problems (e.g., subgraph and induced subgraph counts) are finite linear combinations p(·)=∑_Hα_H(H,·) of homomorphism counts, and such linear combinations are known to be hard to evaluate iff they contain a large-treewidth graph S. The hardness can be shown in two steps: First, the problems (S,·) for colorful (i.e., bijectively colored) large-treewidth graphs S are shown to be hard. In a second step, these problems are reduced to finite linear combinations of homomorphism counts that contain the uncolored version S^∘ of S. This step can be performed via inclusion-exclusion in 2^|E(S)|poly(n,s) time, where n is the size of the input graph and s is the maximum number of vertices among all graphs in the linear combination. We show that the second step can be performed even in time 4^Δ(S)poly(n,s), where Δ(S) is the maximum degree of S. Our reduction is based on graph products with Cai-Fürer-Immerman graphs, a novel technique that is likely of independent interest. For colorful graphs S of constant maximum degree, this technique yields a polynomial-time reduction from (S,·) to linear combinations of homomorphism counts involving S^∘. Under certain conditions, it actually suffices that a supergraph T of S^∘ is contained in the target linear combination. The new reduction yields #𝖯-hardness results for several counting problems that could previously be studied only under parameterized complexity assumptions. This includes the problems of counting, on input a graph from a restricted graph class and a general graph G, the homomorphisms or (induced) subgraph copies from H in G.
READ FULL TEXT