Dichotomy for Graph Homomorphisms with Complex Values on Bounded Degree Graphs

Abstract

The complexity of graph homomorphisms has been a subject of intense study [1], [2], [3], [4], [5], [6], [7], [8]. The partition function Z <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A</sub> (·) 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 → Z <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A</sub> (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, Z <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">A</sub> (·) can be constructed from A, in the respective cases.cases.

Locations

• arXiv (Cornell University) - View - PDF