Dichotomy Result on 3-Regular Bipartite Non-negative Functions

Abstract

We prove a complexity dichotomy theorem for a class of Holant problems on 3-regular bipartite graphs. Given an arbitrary nonnegative weighted symmetric constraint function $f=[x_0,x_1,x_2,x_3]$, we prove that the bipartite Holant problem $\mathrm{Holant}\left(f\mid \left({=}_3\right)\right)$ is \emph{either} computable in polynomial time \emph{or} $\#$P-hard. The dichotomy criterion on $f$ is explicit.

13 pages, 2 figures

Cited by in corpus (1)

• Bipartite 3-Regular Counting Problems with Mixed Signs