Graph Homomorphisms with Complex Values: A Dichotomy Theorem
Graph Homomorphisms with Complex Values: A Dichotomy Theorem
Each symmetric matrix $\mathbf{A}$ over $\mathbb{C}$ defines a graph homomorphism function $Z_{\bf A}(\cdot)$ on undirected graphs. The function $Z_{\mathbf{A}} (\cdot)$ is also called the partition function from statistical physics, and can encode many interesting graph properties, including counting vertex covers and $k$-colorings. We study the computational complexity of $Z_{\mathbf{A}} (\cdot)$ …