Graph Homomorphisms with Complex Values: A Dichotomy Theorem
Preprint
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.Keywords
All Related Versions
This publication has 5 references indexed in Scilit:
- On counting homomorphisms to directed acyclic graphsJournal of the ACM, 2007
- The rank of connection matrices and the dimension of graph algebrasEuropean Journal of Combinatorics, 2006
- Reflection positivity, rank connectivity, and homomorphism of graphsJournal of the American Mathematical Society, 2006
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group TheorySIAM Journal on Computing, 1998
- The Feynman Lectures on PhysicsPhysics Today, 1964