Bipartite 3-Regular Counting Problems with Mixed Signs
share
We prove a complexity dichotomy for a class of counting problems expressible as bipartite 3-regular Holant problems. For every problem of the form Holant(f| =_3 ), where f is any integer-valued ternary symmetric constraint function on Boolean variables, we prove that it is either P-time computable or #P-hard, depending on an explicit criterion of f. The constraint function can take both positive and negative values, allowing for cancellations. The dichotomy extends easily to rational valued functions of the same type. In addition, we discover a new phenomenon: there is a set ℱ with the property that for every f ∈ℱ the problem Holant(f| =_3 ) is planar P-time computable but #P-hard in general, yet its planar tractability is by a combination of a holographic transformation by [[ 1 1; 1 -1 ]] to FKT together with an independent global argument.
READ FULL TEXT