06110685

j

06110685 Cai, Jin-Yi Kowalczyk, Michael Spin systems on $k$-regular graphs with complex edge functions. Theor. Comput. Sci. 461, 2-16 (2012). 2012 Elsevier Science Publishers, Amsterdam EN Holant problem partition function dichotomy theorem holographic algorithms interpolation counting complexity

doi:10.1016/j.tcs.2012.01.021

Summary: Let $k \geq 1$ be an integer and let $h=\left[ \matrix h(0,0) & h(0,1)\\ h(1,0) &h(1,1)\endmatrix \right]$ be a complex-valued symmetric function on domain $\{0,1\}$ (i.e., where $h(0,1)=h(1,0))$. We introduce a new technique, called a syzygy, and prove a dichotomy theorem for the following class of problems, specified by $k$ and $h$: given an arbitrary $k$-regular graph $G=(V,E)$, where the function $h$ is attached to each edge, compute ${\bold Z}(G) = \sum_{\sigma:V \to \{0,1\}} \prod_{\{u,v\} \in E} h(\sigma(u),\sigma(v)). \bold {Z}(\cdotp)$ is known as the partition function of the spin system, also known as counting graph homomorphisms on domain size two, and is a special case of Holant problems. The dichotomy theorem gives a complete classification of the computational complexity of this problem, depending on $k$ and $h$. The dependence on $k$ and $h$ is explicit.