Abstract
Graph homomorphism problem has been studied intensively. Given an m-by-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(G) can encode many interesting graph properties, including counting vertex covers and k-colorings. We study the computational complexity of Z_A(G) for arbitrary complex valued symmetric matrices A. Building on work by Dyer and Greenhill, Bulatov and Grohe, and especially the recent beautiful work by Goldberg, Grohe, Jerrum and Thurley, we prove a complete dichotomy theorem for this problem.