Bipartite 3-Regular Counting Problems with Mixed Signs

Abstract

We prove a complexity dichotomy for a class of counting problems expressible as bipartite 3-regular Holant problems. For every problem of the form $\mathrm{Holant}\left(f\mid {=}_3\right)$, 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 $\mathcal{F}$ with the property that for every $f\in \mathcal{F}$ the problem $\mathrm{Holant}\left(f\mid {=}_3\right)$ is planar P-time computable but #P-hard in general, yet its planar tractability is by a combination of a holographic transformation by $\left[\begin{array}{cc}1& 1\\ 1& -1\end{array}\right]$ to FKT together with an independent global argument.

Accepted by FCT 2021

References in corpus (2)

• Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
• Dichotomy Result on 3-Regular Bipartite Non-negative Functions