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 Z A (·) 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 A (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 A (·) can be constructed from A, in the respective cases. cases.

Authors

• Jin-Yi Cai
• Artem Govorov

Keywords

• Symmetric matrices
• Complexity theory
• Standards
• Task analysis
• Physics
• Partitioning algorithms
• Measurement
• Bounded Degree Graphs
• Symmetric Matrix
• Maximum Degree
• Partition Function
• Simple Graph
• Subject Of Intense Study
• Diagonal Matrix
• Weight Matrix
• Undirected
• Positive Matrix
• Complex Matrix
• Edge Weights
• Non-degenerate
• Abelian Group
• Stringent Conditions
• Tensor Product
• Arithmetic Operations
• Diagonal Entries
• Multiple Edges
• Real Symmetric Matrix
• Root Of Unity
• Prime Power
• Step Of The Proof
• Jordan Form
• Signature Matrix
• Discrete Matrix
• graph homomorphism
• complexity dichotomy
• counting problems
• Vandermonde Argument