On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime Order
share
We study the problem of counting the number of homomorphisms from an input graph G to a fixed (quantum) graph H̅ in any finite field of prime order ℤ_p. The subproblem with graph H was introduced by Faben and Jerrum [ToC'15] and its complexity is still uncharacterised despite active research, e.g. the very recent work of Focke, Goldberg, Roth, and Zivný [SODA'21]. Our contribution is threefold. First, we introduce the study of quantum graphs to the study of modular counting homomorphisms. We show that the complexity for a quantum graph H̅ collapses to the complexity criteria found at dimension 1: graphs. Second, in order to prove cases of intractability we establish a further reduction to the study of bipartite graphs. Lastly, we establish a dichotomy for all bipartite (K_3,3\{e}, domino)-free graphs by a thorough structural study incorporating both local and global arguments. This result subsumes all results on bipartite graphs known for all prime moduli and extends them significantly. Even for the subproblem with p=2 this establishes new results.
READ FULL TEXT