Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs

The complexity of graph homomorphisms has been a subject of intense study [1], [2], [3], [4], [5], [6], [7], [8]. The partition function ZA(·) of graph homomorphism is defined by a symmetric matrix A over C. We prove that the complexity dichotomy of [7] extends to bounded degree graphs. More precisely, we prove that either G → ZA(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 A for this dichotomy is explicit, and can be decided in polynomial-time in the size of A. We also show that the dichotomy is effective in that either a P-time algorithm for, or a reduction from #SAT to, ZA(·) can be constructed from A, in the respective cases.cases.