Each symmetric matrix A defines a graph homomorphism function ZA(⋅), also known as the partition function. We prove that the Bulatov-Grohe dichotomy [4] for ZA(⋅) holds for bounded degree graphs. This resolves a problem that has been open for 15 years. Specifically, we prove that for any nonnegative symmetric matrix A with algebraic entries, either ZA(G) is in polynomial time for all graphs G, or it is #P-hard for bounded degree (and simple) graphs G. We further extend the complexity dichotomy to include nonnegative vertex weights. Additionally, we prove that the #P-hardness part of the dichotomy by Goldberg et al. [12] for ZA(⋅) also holds for simple graphs, where A is any real symmetric matrix.

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.

Graph homomorphism has been an important research topic since its introduction [László Lovász, 1967]. Stated in the language of binary relational structures in that paper [László Lovász, 1967], Lovász proved a fundamental theorem that the graph homomorphism function G ↦ hom(G, H) for 0-1 valued H (as the adjacency matrix of a graph) determines the isomorphism type of H. In the past 50 years various extensions have been proved by Lovász and others [László Lovász, 2006; Michael Freedman et al., 2007; Christian Borgs et al., 2008; Alexander Schrijver, 2009; László Lovász and Balázs Szegedy, 2009]. These extend the basic 0-1 case to admit vertex and edge weights; but always with some restrictions such as all vertex weights must be positive. In this paper we prove a general form of this theorem where H can have arbitrary vertex and edge weights. An innovative aspect is that we prove this by a surprisingly simple and unified argument. This bypasses various technical obstacles and unifies and extends all previous known versions of this theorem on graphs. The constructive proof of our theorem can be used to make various complexity dichotomy theorems for graph homomorphism effective, i.e., it provides an algorithm that for any H either outputs a P-time algorithm solving hom(⋅, H) or a P-time reduction from a canonical #P-hard problem to hom(⋅, H).

We develop a theory of graph algebras over general fields. This is modeled after the theory developed by Freedman, Lovász and Schrijver in [22] for connection matrices, in the study of graph homomorphism functions over real edge weight and positive vertex weight. We introduce connection tensors for graph properties. This notion naturally generalizes the concept of connection matrices. It is shown that counting perfect matchings, and a host of other graph properties naturally defined as Holant problems (edge models), cannot be expressed by graph homomorphism functions over the complex numbers (or even more general fields). Our necessary and sufficient condition in terms of connection tensors is a simple exponential rank bound. It shows that positive semidefiniteness is not needed in the more general setting.