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_{\mathbf{A}}(\cdot )$ of graph homomorphism is defined by a symmetric matrix $\mathbf{A}$ over $\mathbb{C}$. We prove that the complexity dichotomy of [6] extends to bounded degree graphs. More precisely, we prove that either $G \mapsto Z_{\mathbf A}(G)$iscomputableinpolynomial-timeforevery$G$,orforsome$\Delta > 0it is #P-hard over (simple) graphsG$withmaximumdegree$\Delta(G) \le \Delta$\mathrm{.}Thetractabilitycriterionon$\mathbf A$ for this dichotomy is explicit, and can be decided in polynomial-time in the size of $\mathbf{A}$. We also show that the dichotomy is effective in that either a P-time algorithm for, or a reduction from #SAT to, $Z_{\mathbf{A}}(\cdot )$ can be constructed from $\mathbf{A}$, in the respective cases.