Partition functions on k-regular graphs with {0, 1}-vertex assignments and real edge functions

摘要

We prove a complexity dichotomy theorem for a class of partition functions over k-regular graphs, for any fixed k. These problems can be viewed as graph homomorphisms from an arbitrary k-regular input graph G to the weighted two vertex graph on {0, 1} defined by a real-valued symmetric function h. We completely classify the computational complexity of this problem. We show that there are exactly the following alternatives, for any given h. Depending on h, over k-regular graphs, either 1. the problem is #P-hard even for planar graphs, 2. the problem is #P-hard for general (non-planar) graphs, but solvable in polynomial time for planar graphs, or 3. the problem is solvable in polynomial time for general graphs. The dependence on h is an explicit criterion. Furthermore, we show that in case (2) the problem is solvable in polynomial time over k-regular planar graphs, by exactly the theory of holographic algorithms using matchgates.