Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs
The complexity of graph homomorphisms has been a subject of intense study [11, 12, 4, 42, 21, 17, 6, 20]. The partition function Z_π(Β·) of graph homomorphism is defined by a symmetric matrix π over β. We prove that the complexity dichotomy of [6] extends to bounded degree graphs. More precisely, we prove that either G β¦ Z_π(G) is computable in polynomial-time for every G, or for some Ξ > 0 it is #P-hard over (simple) graphs G with maximum degree Ξ(G) β€Ξ. The tractability criterion on π for this dichotomy is explicit, and can be decided in polynomial-time in the size of π. We also show that the dichotomy is effective in that either a P-time algorithm for, or a reduction from #SAT to, Z_π(Β·) can be constructed from π, in the respective cases.
READ FULL TEXT