Graph Homomorphisms with Complex Values: A Dichotomy Theorem

Understand

Graph homomorphism has been studied intensively.

• Given an m x m symmetric matrix A, the graph homomorphism function is defined as \[Z_A (G) = \sum_{f:V->[m]} \prod_{(u,v)\in E} A_{f(u),f(v)}, \] where G = (V,E) is any undirected graph.
• The function Z_A can encode many interesting graph properties, including counting vertex covers and k-colorings.
• We study the computational complexity of Z_A for arbitrary symmetric matrices A with algebraic complex values.