A dichotomy for bounded degree graph homomorphisms with nonnegative weights

Artem Govorov, Jin-Yi Cai, Martin Dyer

We consider the complexity of counting weighted graph homomorphisms defined by a symmetric matrix $A$. Each symmetric matrix $A$ defines a graph homomorphism function $Z_A(\cdot )$,…