# Planar 3-way Edge Perfect Matching Leads to A Holant Dichotomy

Jin-Yi Cai
<EMAIL_ADDRESS>Department of Computer Sciences, University of
Wisconsin–Madison. Austen Z. Fan∗
<EMAIL_ADDRESS>
###### Abstract

We prove a complexity dichotomy theorem for a class of Holant problems on
planar 3-regular bipartite graphs. The complexity dichotomy states that for
every weighted constraint function $f$ defining the problem (the weights can
even be negative), the problem is either computable in polynomial time if $f$
satisfies a tractability criterion, or #P-hard otherwise. One particular
problem in this problem space is a long-standing open problem of Moore and
Robson [MR01] on counting Cubic Planar X3C. The dichotomy resolves this
problem by showing that it is #P-hard. Our proof relies on the machinery of
signature theory developed in the study of Holant problems. An essential
ingredient in our proof of the main dichotomy theorem is a pure graph-
theoretic result: Excepting some trivial cases, every 3-regular plane graph
has a planar 3-way edge perfect matching. The proof technique of this graph-
theoretic result is a combination of algebraic and combinatorial methods.

The P-time tractability criterion of the dichotomy is explicit. Other than the
known classes of tractable constraint functions (degenerate, affine, product
type, matchgates-transformable) we also identify a new infinite set of P-time
computable planar Holant problems; however, its tractability is not by a
direct holographic transformation to matchgates, but by a combination of this
method and a global argument. The complexity dichotomy states that everything
else in this Holant class is #P-hard.

##  1 Introduction

Holant problems are also known as edge-coloring models. They can express a
broad class of counting problems, such as counting matchings, perfect
matchings (#PM), proper edge-colorings, cycle coverings, and a host of
counting orientation problems such as counting Eulerian orientations or the
six-vertex model. Every counting constraint satisfaction problem (#CSP) can be
expressed as a Holant problem. On the other hand, Freedman, Lovász and
Schrijver [FLS07] proved that the prototypical Holant problem #PM cannot be
expressed as a graph homomorphism function (vertex-coloring model) by any real
valued constraint function. This is true even for complex valued constraint
functions [CG19].

Some problems are #P-hard in general, yet computable on planar graphs. The
problem #PM is such a problem [Val79, Jer87]. A most fascinating algorithm—the
FKT algorithm [Kas67, Kas61, TF61]—computes #PM in polynomial time (FP,
polynomial-time computable functions) for planar graphs. Valiant introduced
holographic algorithms which are non-parsimonious reductions to the FKT
algorithm, placing many planar counting problems in FP that seemed to be
intractable. To understand these algorithms a signature theory was developed
and the Holant framework was introduced. Stated in this signature theory,
Valiant’s holographic algorithms boil down to what constraint functions
(signatures) can be realized by the so-called matchgate signatures under a
holographic transformation. Delineating the precise boundary of FP
tractability for these problems has been a central focus in the classification
theory of counting problems [Bac21, CF17, CFGW22, GW20, CLX17, Val08]. A
general theme has emerged: for very broad classes of counting problems, one
can classify every problem in the class to be of exactly one of three types:
(1) FP, (2) #P-hard in general but FP on planar graphs, or (3) #P-hard on
planar graphs. Furthermore, for all #CSP on Boolean variables (which includes
vertex models), Valiant’s holographic algorithm is a universal algorithm
[CF17] that solves problems in (2)111However, this is not true for Holant
problems in general [CFGW22]. If one recalls that the FKT algorithm solves #PM
for planar graphs, which is _the_ prototypical Holant problem but not a vertex
model, this is particularly intriguing.. In this paper, we prove that for a
class of bipartite Holant problems, this three-way classification _holds_.
However, there are _two methods_ for planar tractability in type (2): In
addition to holographic transformations to matchgates, there is another type
which combines this transformation with a global argument. Either method alone
is not, but _together_ they do form, a universal strategy for planar
tractability.

We briefly define Holant problems on Boolean variables. An input is a
signature grid $\Omega$ consisting of a graph $G=(V,E)$ with each vertex $v$
labeled by a constraint function $f_{v}$ (also called a signature). The Holant
problem is to compute a sum-of-product
$\operatorname{Holant}(\Omega)=\sum_{\sigma:E\rightarrow\\{0,1\\}}\prod_{v\in
V}f_{v}(\sigma|_{E(v)})$, where $E(v)$ denotes the incident edges of $v$.
E.g., #PM is the counting problem where each $f_{v}$ is the 0-1 valued Exact-
One function. In planar Holant problems, denoted by $\operatorname{Pl-
Holant}$, $G$ is required to be planar, and $f_{v}$ takes inputs from $E(v)$
which is given a cyclic order starting from some edge (specified by $\Omega$).

In this paper, we study a class of Holant problems whose input graphs are
planar, 3-regular and bipartite. More precisely, let
$f(x,y,z)=[f_{0},f_{1},f_{2},f_{3}]$ be any ternary constraint function which
takes value $f_{i}\in{\mathbb{Q}}$, if the input has Hamming weight $i$. We
allow both positive and negative values. We study $\operatorname{Pl-
Holant}\left(f\mid(=_{3})\right)$, the Holant problem on planar, 3-regular
bipartite graphs where LHS vertices are assigned $f$ and RHS vertices are
assigned a ternary equality $(=_{3})$. Without planarity, a complexity
dichotomy was proved for these bipartite Holant problem in [CFL23]. Planarity
plus regularity add considerable difficulty.

One can think of them as counting problems on 3-regular 3-uniform hypergraphs,
or set systems where every subset has cardinality 3 and every element appears
in 3 subsets. The planarity refers to its (bipartite) incidence graph. These
include some well studied problems. One long-standing open problem raised by
Moore and Robson in [MR01] is counting Cubic-Planar-X3C, (X3C stands for
Exact-3-Cover), or equivalently Cubic Planar Monotone 1-in-3 SAT. Expressed as
a Holant problem it is $\operatorname{Pl-
Holant}\left([0,1,0,0]\mid(=_{3})\right)$, where $[0,1,0,0]$ is the ternary
Exact-One function. Schaefer [Sch78] proved that Monotone 1-in-3 SAT is NP-
complete. Lichtenstein [Lic82] first considered the complexity of many planar
problems, and Laroche [Lar93] proved that Planar Monotone 1-in-3 SAT is NP-
complete. Monotone 1-in-3 SAT is the same as X3C. Dyer and Frieze [DF86]
proved the NP-completeness of Planar X3C and 3DM where each element is in
either 2 or 3 subsets (of cardinality 3). Moore and Robson [MR01], in a
reduction using ingenious combinatorial gadgets, showed that this problem
remains NP-complete when each element is in exactly 3 subsets. However, they
noted that they were not able to conclude the #P-hardness of its counting
version, which is precisely $\operatorname{Pl-
Holant}\left([0,1,0,0]\mid(=_{3})\right)$, while all previous NP-complete
proofs listed here do extend to #P-hardness for its counting version. We
observe that these proofs are combinatorial, and they become increasingly more
delicate with planarity and regularity restrictions.

Our proof is carried out using the machinery of signature theory developed in
the study of Holant problems. These are algebraic proofs which show that the
underlying combinatorial constructions succeed. This machinery demonstrates
the power of using algebraic method to prove complexity results which are
combinatorial in nature. Indeed, this is exactly in the spirit of Valiant’s
holographic algorithms which use arithmetic cancellations to achieve
reductions that are globally valid for counting, but solutions do not
correspond in a 1-1 fashion (i.e., non-parsimonious reductions).

One difficulty in working with 3-regular bipartite Holant problems is the
severe limitation on the gadgets that can be possibly constructed. One can
show that on either side of the bipartite problem, every constructible gadget
defines a constraint function having arity a multiple of 3. So in particular,
one cannot directly produce unary signatures, or binary signatures on either
side. One _can_ produce “straddled” signatures that take some input variables
from one side and some from the other. Typically a “degenerate” signature is
not very useful in the proof of a dichotomy theorem. A counter-intuitive idea
from [CFL23] is to utilize straddled and degenerate signatures, to “virtually”
produce unary signatures. This idea led to a complexity dichotomy for these
bipartite counting problems in the setting that ignores planarity. But the
essence of Valiant’s holographic algorithm and the study of Holant problems is
to account for planar tractability, and we know there are problems in this
class that are #P-hard in general but in FP on planar graphs.

In this paper we settle that by proving a planar complexity dichotomy. A major
technical challenge is how to “virtually” produce unary signatures in a planar
way. We prove a pure graph-theoretic result that says that, except in some
trivial cases, every 3-regular plane graph 222 A 3-regular graph is also
called a cubic graph. Properties of cubic planar graphs have been studied
extensively [HM88, ABHM00, NRR20, HT06, Sch74].  has a planar 3-way edge
perfect matching (P3EM). We use it as an essential ingredient to the proof of
the dichotomy. This result should be of independent interest. The proof
technique to prove this matching theorem is a combination of algebraic and
combinatorial methods. This theorem lets us virtually “manufacture” and then
“absorb” unary signatures in the #P-hardness reduction. This allows us to
carry out the needed #P-hardness reductions in a planar way.

##  2 Preliminaries and Our Main Theorem

A (symmetric) constraint function (a.k.a. signature) of arity $n$ is
$f=[f_{0},f_{1},\ldots,f_{n}]$, where $f_{i}$ denotes the function value on
inputs of Hamming weight $i$. E.g., the ternary Exact-One function is
$[0,1,0,0]$, and the ternary Equality function $\left(=_{3}\right)$ is
$[1,0,0,1]$. In this paper we consider the following set of
$\operatorname{Holant}$ problems, denoted by $\operatorname{Pl-
Holant}\left(f\mid(=_{3})\right)$, where $f$ is a ternary function. An input
is a signature grid $\Omega$ consisting of a planar 3-regular bipartite graph
$G=(U,V,E)$, where each vertex in $U$ is assigned
$f=[f_{0},f_{1},f_{2},f_{3}]$ with values $f_{i}\in\mathbb{Q}$, and each
vertex in $V$ is assigned $\left(=_{3}\right)$. The Holant problem is to
compute

$\operatorname{Holant}\left(\Omega\right)=\sum_{\sigma:E\rightarrow\\{0,1\\}}\prod_{u\in
U}f\left(\sigma|_{E(u)}\right)\prod_{v\in
V}\left(=_{3}\right)\left(\sigma|_{E(v)}\right).$

For clarity, we shall call vertices in $U$ are on the left hand side (LHS) and
vertices in $V$ are on the right hand side (RHS). We can write a signature of
arity $n$ as a vector in $\mathbb{Q}^{2^{n}}$ indexed in lexicographical
order. A (symmetric) signature $f$ is degenerate if there exists a unary
signature $u\in\mathbb{C}^{2}$ such that $f=u^{\otimes n}$, the $n$th tensor
power.

The main result of this paper is the following dichotomy theorem:

######  Theorem 2.1.

$\operatorname{Pl-Holant}\left(f\mid(=_{3})\right)$ where
$f=[f_{0},f_{1},f_{2},f_{3}]$ and $f_{i}\in\mathbb{Q}$ ($0\leq i\leq 3$) is
#P-hard except in the following cases, for which the problem is in
$\operatorname{FP}$: (1) $f$ is degenerate; (2) $f=[a,0,0,b]$, for some $a,b$;
(3) $f=[a,0,\pm a,0],[0,a,0,\pm a],[a,-a,-a,a],[a,a,-a,-a]$ for some $a$; (4)
$f=[a,b,b,a]$ or $f=[a,b,-b,-a]$, for some $a,b$; (5)
$f=[3a+b,-a-b,-a+b,3a-b]$ for some $a,b$. Without the planar restriction, the
problem $\operatorname{Holant}(f\,|\,(=_{3}))$ remains in $\operatorname{FP}$
in cases (1), (2) and (3), but #P-hard in cases (4) and (5).

In case (1), the signature $f$ decomposes into three unary signatures. In case
(2), $f$ is a generalized equality. In case (3), $f$ is in the affine class.
In case (4), the Holant problem is transformable to planar #PM with matchgates
(see more details about these tractable classes in [CC17]). In case (5), the
planar P-time tractability is _neither_ by Valiant’s holographic reduction
alone, _nor_ entirely independent from it. Rather it is by a combination of a
holographic reduction together with a global argument.

As mentioned in Section 1, counting Cubic-Planar-X3C is just
$\operatorname{Pl-Holant}\left([0,1,0,0]\mid(=_{3})\right)$, the counting
problem of Moore and Robson [MR01]. It clearly belongs to this class. It is
also equivalent to Cubic Planar Monotone 1-in-3 SAT. By Theorem 2.1, it is
#P-complete.

To see that case (5) is planar tractable, we prove for any $a$ and $b$, the
value of $\operatorname{Pl-Holant}\left(f\mid(=_{3})\right)$ for
$f=[3a+b,-a-b,-a+b,3a-b]$ on any planar signature grid exactly equals the
value of $\operatorname{Pl-Holant}\left([0,2a,0,0]\mid[0,1,0,0]\right)$ on the
same signature grid, and thus can be computed by the FKT algorithm for
counting perfect matchings. Indeed, by a holographic transformation using
$H=\left[\begin{smallmatrix}1&1\\\ 1&-1\end{smallmatrix}\right]$ we have the
following sequence of equivalences:

$\displaystyle\operatorname{Pl-Holant}\left(f\mid(=_{3})\right)$
$\displaystyle\equiv_{T}$ $\displaystyle\operatorname{Pl-
Holant}\left(fH^{\otimes 3}\mid(H^{-1})^{\otimes 3}(=_{3})\right)$
$\displaystyle\equiv_{T}$ $\displaystyle\operatorname{Pl-
Holant}\left([0,0,2a,2b]\mid[1,0,1,0]\right)$ $\displaystyle\equiv_{T}$
$\displaystyle\operatorname{Pl-Holant}\left([0,0,2a,0]\mid[0,0,1,0]\right)$
$\displaystyle\equiv_{T}$ $\displaystyle\operatorname{Pl-
Holant}\left([0,2a,0,0]\mid[0,1,0,0]\right)$

where the third equivalence follows from the observation that for each nonzero
term in the Holant sum, every vertex on the LHS has at least two of three
edges assigned 1 (from $[0,0,2a,2b]$), meanwhile every vertex on the RHS has
at most two of three edges assigned 1 (from $[1,0,1,0]$). The graph being
bipartite and 3-regular, the number of vertices on both sides must equal, thus
every vertex has exactly two incident edges assigned 1.

An example of a planar tractable problem that belongs to case (5) is as
follows. It can be viewed as a covering problem on 3-uniform hypergraphs of
degree 3. We say $(X,{\cal S})$ is a 3-regular $k$-uniform set system (or
3-regular $k$-uniform hypergraph), if ${\cal S}$ consists of a family of sets
$S\subset X$ each of size $|S|=k$, and every $x\in X$ is in exactly 3 sets. If
$k=2$ this is just an ordinary 3-regular graph (where the $2$-subsets are
ordinary edges). We consider 3-regular $3$-uniform set systems. We say ${\cal
S^{\prime}}$ is a _leafless partial cover_ if every $x\in\bigcup_{S\in{\cal
S^{\prime}}}S$ belongs to more than one set $S\in{\cal S^{\prime}}$. We say
$x$ is _lightly covered_ if $|\\{S\in{\cal S^{\prime}}:x\in S\\}|$ is 2, and
_heavily covered_ if this number is 3.

$\mathbf{Problem:}$ Weighted-Leafless-Partial-Cover.

$\mathbf{Input:}$ A 3-regular $3$-uniform set system $(X,{\cal S})$.

$\mathbf{Output:}$ $\sum_{\cal S^{\prime}}(-1)^{l}2^{h}$, where the sum is
over all leafless partial covers ${\cal S^{\prime}}$, and $l$ (resp. $h$) is
the number of $x\in X$ that are lightly covered (resp. heavily covered).

Expressed in the Holant framework this problem is just
$\operatorname{Holant}\left(f\mid(=_{3})\right)$, where $f=[1,0,-1,2]$. This
problem belngs to case (5) with $a=1/2$ and $b=-1/2$.

Figure 1: A small instance for the problem Weighted-Leafless-Partial-Cover

Figure 1 illustrates a small instance of this problem. Blue dots represent
elements $x$ and red dots represent the family of sets $S$. An element $x$ is
contained in a set $S$ if and only if the blue dot for $x$ is connected to the
red dot for $S$. It is not hard to see that there are exactly 6 leafless
partial covers, which are $\emptyset$, any family of 3 sets (there are 4 of
them), and the family of all 4 sets. Therefore, the Holant value of this
instance is $1+4(-1)^{3}2^{1}+2^{4}=9$. One can also verify that there are
exactly 9 distinct perfect matchings in the graph in Figure 1.

Therefore, it is known that cases (1)–(5) are in $\operatorname{FP}$. The main
claim lies in that all other cases are #P-hard over planar graphs. The cases
(4) and (5) capture precisely those problems that are #P-hard on general but
in FP on planar graphs; neither case alone does that.

A gadget in this paper, such as those illustrated in Figure 19 and Figure 26,
is a planar 3-regular bipartite graph $G=(U,V,E_{\rm in},E_{\rm out})$ with
internal edges $E_{\rm in}$ and dangling edges $E_{\rm out}$. There can be $m$
dangling edges internally incident to vertices from $U$ and $n$ dangling edges
internally incident to vertices from $V$. These $m+n$ dangling edges
correspond to Boolean variables $x_{1},\ldots,x_{m},y_{1},\ldots,y_{n}$ and
the gadget defines a signature

$f(x_{1},\ldots,x_{m},y_{1},\ldots,y_{n})=\sum_{\sigma:E_{\rm
in}\rightarrow\\{0,1\\}}\prod_{u\in
U}f\left(\widehat{\sigma}|_{E(u)}\right)\prod_{v\in
V}\left(=_{3}\right)\left(\widehat{\sigma}|_{E(v)}\right),$

where $\widehat{\sigma}$ denotes the extension of $\sigma$ by the assignment
on the dangling edges. The variables $x_{1},\ldots,x_{m}$ (respectively,
$y_{1},\ldots,y_{n}$) are called LHS (respectively, RHS) variables and are to
be connected externally to RHS (respectively, LHS) signatures in
$\operatorname{Pl-Holant}\left(f\mid(=_{3})\right)$.

Gadgets that are constructible for $\operatorname{Pl-
Holant}\left(f\mid(=_{3})\right)$ is severely limited due to planarity and
bipartiteness. Suppose $g$ is the signature of a gadget construction with all
of its variables on the LHS. Then by a simple counting argument, the arity of
$g$ must be a multiple of 3. The same is true for a gadget construction with
all of its variables on the RHS. In particular, one cannot hope to produce any
unary or binary signature on either side. However, being able to have unary or
binary signatures at hand has been proven to be very useful in studying Holant
problems.

To tackle this difficulty, straddled gadgets were introduced [CFL23] which
have both LHS and RHS variables. For example, the gadget $G_{1}$ in Figure 19,
after we place $f$ on the square vertex and $(=_{3})$ on the circle vertex,
has one variable on the LHS (the dangling edge that connects to a square) and
one variable on the RHS (the dangling edge that connects to a circle). We list
the values of a signature $f$ in a signature matrix $M_{f}$ where the row(s)
$R$ and column(s) $C$ correspond to assignments, in lexicographic order, of
input variables $X=R\mathbin{\mathaccent 0{\cdot}\cup}C$. We may identify $f$
with $M_{f}$. When two signatures $M_{f}$ and $M_{g}$ are composed by merging
the dangling edges of the column variables of $f$ with the row variables of
$g$, the signature matrix of the resulting signature is the matrix product
$M_{f}M_{g}$. In our paper, the composition must respect the bipartiteness and
planarity. Also, note that if a straddled gadget has $m$ dangling edges to be
connected to RHS and $n$ dangling edges to be connected to LHS, then
$m-n\equiv 0\bmod 3$.

One crucial idea in [CFL23] is to interpolate _degenerate_ straddled binary
signatures and use them as two unary signatures; one of which is desired and
the other is to be grouped together to form an easily computable positive
constant, which does not affect the complexity. However, the “grouped
together” process destroys the planar structure and thus the reduction fails
for planar graphs. However, we can make it work for planar graphs if we can
group these leftover unaries three at a time within each face. This is where
planar 3-way edge matching (P3EM) comes in. Our theorem on P3EM will allow us
to do that.

More formally, let $G=(V,E)$ be an undirected plane graph, i.e., a planar
graph with a given planar embedding. We allow $G$ to be a multi-graph, i.e.,
parallel edges and self-loops are allowed. A planar 3-way edge matching (P3EM)
is a partition of $E$ into a collection $M$ of 3-edge subsets $E=\bigcup_{t\in
M}t$ such that we can add one vertex $v_{t}$ for each $t\in M$ and connect
$v_{t}$ to the three edges of $E$ in $t$ so that the resulting graph is still
a plane graph. In Section 3, we prove that a P3EM always exists for any plane
3-regular graph (except for some trivial cases) and, moreover, can be
constructed in polynomial time. An often-used technique in dealing with plane
graphs is first taking a spanning tree of the dual graph and picking a root
node, e.g., the node associated to the outer face. Starting from a leaf, one
argues that some invariant property can be “propagated” through the tree until
finally reaching the root. This technique is used in [MR01] as well as in the
proof of previous dichotomies concerning planarity [CF17, CFGW22]. However,
this technique does not work in this case. New techniques have to be invented.
The proof of our P3EM theorem is a mixture of algebra and combinatorics, and
it should be of independent interest.

##  3 Planar 3-way Edge Matching (P3EM)

We begin with the following lemma.

######  Lemma 3.1.

A 3-regular plane graph $G$ has a P3EM iff there is an assignment that assigns
each edge to an adjacent face so that the number of edges assigned to each
face is $0\bmod 3$.

###### Proof.

If $E=\bigcup_{t\in M}t$ is a P3EM, then for every 3-edge subset $t\in M$, the
point $v_{t}$ belongs to a face adjacent to all three edges in $t$. This gives
the assignment of $E$.

Conversely, suppose there is such an assignment $\sigma$ for $G$, and we first
assume $G$ is a connected plane graph. Then a partition of $E$ into 3-edge
subsets can be obtained by collecting consecutive triples from edges that are
assigned toward any face $F$ along a cyclic traversal of the boundary of $F$.
This produces a P3EM for $G$.

Now suppose $G$ is disconnected and we consider $G$ as given on the sphere
$S^{2}$. There is a simple closed curve $S$ (homeomorphic to a circle $S^{1}$)
disjoint from $G$ separating $S^{2}$ into two discs $D_{1}$ and $D_{2}$, and
separating $G$ into two nonempty disjoint plane graphs $G_{1}\cup G_{2}$, with
$G_{i}\subset D_{i}$ ($i=1,2$). $S$ is contained in some face $F$. For
$i=1,2$, every face other than $F$ in $D_{i}$ is assigned by $\sigma$ edges
from $E(G_{i})$ only, and the number of which is $0\bmod 3$. Since $G_{i}$ is
3-regular, we have $|E(G_{i})|\equiv 0\bmod 3$. Hence the number of edges from
$E(G_{i})$ assigned to $F$ is also $0\bmod 3$. Thus the restriction of
$\sigma$ to $E(G_{i})$ is an edge assignment for $G_{i}$ that satisfies the
stipulation in the lemma statement. Formally, for $G_{1}$ we can remove
$G_{2}$, then $F$ becomes an extended face $\widehat{F}$ containing $D_{2}$,
and we get an assignment $\sigma_{1}$ from $E(G_{1})$ to the set of faces of
$G$ in $D_{1}$ together with $\widehat{F}$. For $G_{1}$ we can contract
$D_{2}$ to a single point, and $\widehat{F}$ becomes essentially the
intersection of $F$ with $D_{1}$. Similarly we have an assignment $\sigma_{2}$
for $G_{2}$.

By induction, we have a P3EM for both $G_{1}$ and $G_{2}$, made up of triples
of edges of $G_{1}$ and $G_{2}$ separately. Due to the contraction of $D_{2}$
for $G_{1}$ the triples $t$ assigned to $F$ from $G_{1}$ correspond to points
$v_{t}$ inside $D_{1}$. The same statement is true for $G_{2}$. This removes
any potential interference with planarity when putting the two P3EMs together
to form a P3EM for $G$. ∎

Thus to prove the existence of a P3EM of $G$ we will prove the existence of
such an assignment. It also follows that $G$ has a P3EM iff each connected
component of $G$ does.

Plane graphs $G_{i}=(V_{i},E_{i})$, $(i=1,2)$, are planarly isomorphic if
there exists an 1-1 correspondence of $V_{1}$ and $V_{2}$ such that it induces
a 1-1 correspondence of the edges and faces by incidence. Clearly, having a
P3EM is a property preserved by planar isomorphism.

######  Theorem 3.2.

Every 3-regular plane graph, except for those containing a connected component
$K_{4}$ or the multi-graph $M_{2,3}$ on 2 vertices with 3 parallel edges,
admits a planar 3-way edge matching, and one can be found in polynomial time.

We note that P3EM indeed does not exist for the two exceptional graphs. Also,
up to planar isomorphism there is only one plane embedding for these two
graphs, as well as all graphs depicted in Figure 2, which will serve as our
induction base cases. In Figure 2, edges of the same color form a triple.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Figure 2: Base cases in the proof of Theorem 3.2

###### Proof.

By Lemma 3.1, it suffices to prove the case when $G$ is connected, as putting
together P3EMs for each connected component gives a P3EM for $G$.

We prove Theorem 3.2 by induction. Our induction hypothesis is as follows: if
$|V(G)|\leq k$ for some integer $k$ and it is not one of the two exceptions,
then it admits a P3EM. Given a larger graph $G$, we try to reduce it to a
smaller graph $G^{\prime}$ such that we obtain a P3EM for $G$ from that of
$G^{\prime}$; whenever the reduction step produces one of the two exceptions,
we will give a P3EM directly to the original graph.

$A$$B$$C$$D$$e_{1}$$e_{2}$$e_{4}$$e_{3}$ (a) self loop in the original graph

$C$$D$$e^{*}$ (b) resulting graph

Figure 3: Transforming self-loops

We first show it suffices to consider simple planar 3-regular graphs.

If $G$ has a self-loop, then locally it has a fragment depicted in Figure 3,
unless it is planarly isomorphic to the base case Figure 2(a), which we
directly give a P3EM. Now perform the transformation depicted in Figure 3. If
the resulting graph is one of the two exceptions, then the original graph is
planarly isomorphic to the base cases Figure 2(b) or Figure 2(c), for which we
give their P3EMs directly. Otherwise, by induction hypothesis, there exists a
P3EM $M$ for the resulting graph. If the edge $e^{*}$ in Figure 3b is mapped
rightwards (resp. leftwards) in $M$, then we obtain a P3EM for the original
graph by simulating $e_{4}$ as $e^{*}$ to be mapped rightwards (resp.
leftwards) and connecting $e_{1}$, $e_{2}$ and $e_{3}$. Note that the self-
loop transformation is valid regardless whether there is a self-loop at the
vertices $C$ or $D$.

$A$$e_{1}$$B$$e_{2}$$e_{3}$$C$$e_{4}$$D$ (a) double edges in the original
graph

$A$$e^{*}$$D$ (b) resulting graph

Figure 4: Transforming double edges

If $G$ has parallel edges between two vertices, say $B$ and $C$, since $G$ is
3-regular and $G$ is not planarly isomorphic to $M_{2,3}$, there must be
exactly two edges between them. If $B$ and $C$ have a common neighbor, say
$A$, we may delete $B,C$ and their incident edges, and add a self-loop at $A$.
The resulting graph is not one of the exceptions, by induction, it has a P3EM.
One can then easily obtain a P3EM for $G$. Now suppose the third edges from
$B$ and $C$ are $e_{1}=\\{A,B\\}$ and $e_{4}=\\{C,D\\}$ with $A\neq D$, as
depicted in Figure 4. We likewise perform a transformation which “deletes” $B$
and $C$ with double edges, and merge $e_{1}$ and $e_{4}$ to a single edge
$e^{*}=\\{A,D\\}$. If the resulting graph is one of the two exceptions, the
original graph is isomorphic to the base cases Figure 2(d) or Figure 2(e)
which we give their P3EMs directly. Otherwise, by induction hypothesis, there
exists a P3EM $M$ for the resulting graph. If the edge $e^{*}$ is mapped
upward (resp. downward) in $M$ (Figure 4b), then we obtain a P3EM for the
original graph by simulating $e_{2}$ (resp. $e_{3}$) as $e^{*}$ and connecting
$e_{3}$ (resp. $e_{2}$), $e_{1}$ and $e_{4}$.

Below we assume $G$ is simple, i.e., without parallel edges or self-loops.

$A$$B$$C$$D$$E$$F$$e_{1}$$e_{2}$$e_{3}$ (a) triangle in the original graph

$D$$E$$F$$e_{1}$$e_{2}$$e_{3}$ (b) resulting graph

$A$$B$$C$$D$$F$$E^{\prime}$ (c) triangle in the original graph ($D=E$)

$F$$E^{\prime}$ (d) resulting graph ($D=E$)

Figure 5: Transforming triangles

Next we consider the case when $G$ contains a triangle face as depicted in
Figure 5(a). Since it is a simple graph, all three edges $e_{1},e_{2},e_{3}$
are distinct, and $D,E,F\not\in\\{A,B,C\\}$. If the vertices $D,E,F$ are all
distinct, then we perform the transformation from Figure 5(a) to Figure 5(b).
By induction hypothesis, the resulting graph admits a P3EM unless it is
$K_{4}$ (in this case, the resulting graph cannot be $M_{2,3}$ since it has
more than two vertices). If the resulting graph is $K_{4}$, then the original
graph is (or planarly isomorphic to) the base case Figure 2(f) for which we
give a P3EM directly. If the resulting graph is not $K_{4}$ and hence admits a
P3EM $M$ by our induction hypothesis, then the original graph can simulate $M$
by connecting the edges of the triangle face internally. We now consider the
case when the vertices $D,E,F$ are not all distinct. Since the original graph
is not $K_{4}$, the vertices $D,E,F$ are not all the same vertex. Without loss
of generality we assume $D=E\neq F$. See Figure 5(c) for an illustration. $D$
has an incident vertex $E^{\prime}\neq A,B$. Suppose $E^{\prime}\neq F$. Then
we perform the transformation illustrated in Figure 5(d). Similarly as above,
if the resulting graph is not one of the exceptions, then we can easily
simulate the P3EM (which is given by the induction) in the resulting graph. If
the resulting graph Figure 5(d) is planarly isomorphic to the exceptions
$M_{2,3}$ or $K_{4}$, then the original graph is planarly isomorphic to the
base cases Figure 2(g) or Figure 2(h), which we give a P3EM directly. Finally
suppose $E^{\prime}=F$, then we transform the original graph by deleting the
vertices $A,B,C,D$ and their incident edges, and form a self-loop at
$E^{\prime}=F$. The resulting graph has fewer vertices (and has a self-loop
and so it is not $M_{2,3}$ or $K_{4}$), and so by the induction hypothesis it
admits a P3EM. It is easy to verify that a P3EM in the resulting graph, as
before, can be simulated in the original graph. In the following we may assume
$G$ is simple without triangle faces.

$B$$A$$C$$E$$D$$F$ (a) bridge in the original graph

$A$$C$$D$$F$ (b) resulting graph

Figure 6: Transforming a bridge

Next we consider the case when the graph contains a bridge, i.e., an edge
whose removal disconnects the graph (see Figure 6a). This means that the same
face $f$ is on both sides of the bridge $\\{B,E\\}$ in $G$. Perform the
transformation illustrated in Figure 6. The resulting graph has two
disconnected components which are not isomorphic to any exception case.
Indeed, neither is isomorphic to $M_{2,3}$ since $G$ has no parallel edges,
and if it were $K_{4}$ then the original graph $G$ contains a triangle face.
Thus by induction there are P3EMs, $M_{1}$ and $M_{2}$, for the two components
respectively. We will use the edges $\\{B,C\\}$ and $\\{E,F\\}$ to simulate
$\\{A,C\\}$ and $\\{D,F\\}$ respectively, and match the three edges
$\\{A,B\\},\\{B,E\\}$ and $\\{E,D\\}$ directly. Then we obtain a P3EM for $G$
from $M_{1}$ and $M_{2}$. Note that both $\\{B,C\\}$ and $\\{E,F\\}$ are on
the face $f$. Since $\\{B,E\\}$ is a bridge, regardless of how $\\{A,C\\}$ and
$\\{D,F\\}$ are matched respectively by $M_{1}$ and $M_{2}$, we can substitute
$\\{B,C\\}$ and $\\{E,F\\}$ for them respectively. When viewed in a spherical
embedding, we may assume both $\\{A,C\\}$ and $\\{D,F\\}$ are on the outer
face for the two disconnected components. Then in $G$ the substitution of
$\\{B,C\\}$ for $\\{A,C\\}$, and $\\{E,F\\}$ for $\\{D,F\\}$, gives a total
number of edges assigned to the face $f$ in $G$ to be the sum of the
corresponding numbers assigned by $M_{1}$ and $M_{2}$, and thus this total
number is $\equiv 0\pmod{3}$. Below we assume the graph has no bridges.

$A$$B$$C$$D$$E$$F$$H$$I$ (a) square in the original graph

$I$$H$$E$$F$$e$ (b) resulting graph

Figure 7: Transforming a square

We show next that if $G$ has a square face, then it admits a P3EM. See Figure
7 for an illustration. Since it is simple, $E$ is distinct from $B,D$. Also
$E\neq C$, for otherwise $\\{B,F\\}$ or $\\{D,I\\}$ would be a bridge. By the
same reason, none of the vertices $E,F,H,I$ can be from $\\{A,B,C,D\\}$. If
$E=H$ we again would have a bridge. Also $E\neq F,I$, because $G$ has no
triangle face. It follows that all $A,B,C,D,E,F,H,I$ are distinct. Now we
perform the transformation in Figure 7, replacing the square $ABCD$ by an edge
$e$. It is clearly not one of the exception graphs (it has at least 6
vertices). By induction hypothesis, the resulting graph admits a P3EM $M$. If
$e$ in the resulting graph is mapped leftwards, then we can simulate $M$ in
$G$ by mapping $\\{A,B\\}$ leftwards, and match $\\{A,D\\}$, $\\{D,C\\}$ and
$\\{C,B\\}$ inside the square. Similarly, if $e$ is mapped rightwards, then we
use $\\{D,C\\}$ in its place, and match $\\{A,D\\}$, $\\{A,B\\}$ and
$\\{B,C\\}$ inside the square. This gives a P3EM for $G$. Below we assume $G$
has no square faces.

$A$$B$$C$$D$$E$$F$$1$$2$ (a) chord in the original graph

$E^{\prime}$$A$$B$$C$$D$$F^{\prime}$$F$$E$ (b) resulting graph

Figure 8: Transforming a chord

We now consider the case when the graph contains a chord. Let $\mathcal{C}$ be
the boundary of the external face of the plane graph. Since we can now assume
$G$ is bridgeless, $\mathcal{C}$ is a simple cycle. We say it contains a chord
if there exist two vertices on $\mathcal{C}$ that are joined by an edge that
is not in $\mathcal{C}$. See Figure 8a for an illustration. Since
$\mathcal{C}$ is the outer boundary, any chord must connect inside of
$\mathcal{C}$. Let $\\{A,B\\}$ be a chord, and let $C,E$ and $D,F$ be their
neighbors on $\mathcal{C}$. We note that there is no edge connecting
$\\{C,D\\}$ or $\\{E,F\\}$ since $G$ has no square face. In Figure 8a we mark
the part of $G$ to the left, respectively to the right, of (but including) the
edge $\\{A,B\\}$ as region 1, respectively region 2. By planarity, the only
edges connecting regions 1 and 2 are those incident to $A$ or $B$. Denote the
numbers of edges in regions 1 and 2 by $E_{1}$ and $E_{2}$ (both including
$\\{A,B\\}$). Then $E_{1}+E_{2}\equiv 1\pmod{3}$. Perform the transformation
illustrated in Figure 8 and we obtain a resulting graph that is disconnected
and its two components are 3-regular plane graphs. Since in the original
graph, $E$ and $F$ are not adjacent, there exists another vertex distinct from
$E$ and $F$ in region 2. Thus, the left side component in the resulting graph
has at least one vertex fewer than $G$, and by induction hypothesis it admits
a P3EM $M^{\prime}_{1}$. Similarly, the right side component also admits a
P3EM $M^{\prime}_{2}$ (it cannot be $M_{2,3}$ since $G$ is simple, nor $K_{4}$
since that will imply $G$ has a triangle face). The edge
$\\{E^{\prime},F^{\prime}\\}$ is assigned either inside the triangle
$AE^{\prime}F^{\prime}$ or inside $BE^{\prime}F^{\prime}$. In the former case,
the edges $\\{B,E^{\prime}\\}$ and $\\{B,F^{\prime}\\}$ must be assigned
outside the triangle $BE^{\prime}F^{\prime}$. In the latter case, the edges
$\\{A,E^{\prime}\\}$ and $\\{A,F^{\prime}\\}$ are assigned outside the
triangle $AE^{\prime}F^{\prime}$. In either case, exactly one of the edges
$\\{A,E^{\prime}\\}$ or $\\{B,E^{\prime}\\}$ is assigned leftwards and one of
the edges $\\{A,F^{\prime}\\}$ or $\\{B,F^{\prime}\\}$ is assigned outside.
Thus, there are $N_{1}\equiv 2\pmod{3}$ edges in the path $(A,C,\dots,D,B)$
along the cycle $\mathcal{C}$ assigned outside. Similarly, let $N_{2}$ denote
the number of edges assigned outside along the external face in
$M^{\prime}_{2}$, then $N_{2}\equiv 0\pmod{3}$. We now construct a 3DEM in
$G$. In region 1, the edge $\\{A,B\\}$ will be assigned leftwards (taking its
place as either $\\{A,E^{\prime}\\}$ or $\\{B,E^{\prime}\\}$ which was
assigned leftwards in $M^{\prime}_{1}$). All other edges will be assigned in
the same way as in $M^{\prime}_{1}$. In region 2 we assign all edges, other
than $\\{A,B\\}$, as follows. The edge $\\{B,F\\}$ will be assigned outside
(taking its place as either $\\{A,F^{\prime}\\}$ or $\\{B,F^{\prime}\\}$ which
was assigned outside in $M^{\prime}_{1}$); $\\{A,E\\}$ will be assigned as
$\\{E,F\\}$ in $M^{\prime}_{2}$; all other edges will be assigned the same way
as in $M^{\prime}_{2}$. By doing so, all internal faces are assigned
$0\pmod{3}$ edges, as in the case of $M^{\prime}_{1}$ and $M^{\prime}_{2}$.
For the external face, note that there are also $N_{1}+1+N_{2}\equiv
0\pmod{3}$ edges assigned to it in total. Thus our construction gives a valid
P3EM in $G$.

To summarize, we can assume now that the 3-regular plane graph $G$ is simple,
without triangle and square faces, bridgeless and chordless. We now show that
the graph must have a pentagon face. Let $v,e,f$ denote the number of
vertices, edges and faces (including the external one) of $G$, respectively.
Since $G$ is 3-regular, we have $3v=2e$. Suppose the minimum number of edges
around any face is $n$, then $2e\geq nf$. By Euler’s formula, we have
$2=v-e+f\leq(2/n-1/3)e$, and thus $n<6$. Since $G$ is simple and without
triangle and square faces, we have $n=5$.

$P$$a_{0}$$a_{1}$$a_{2}$$a_{4}$$a_{3}$$b_{0}$$b_{1}$$b_{2}$$b_{4}$$b_{3}$
Figure 9: Pentagon in the original graph

Now fix a pentagon face $P$ in the graph with vertices
$\\{a_{0},a_{1},\ldots,a_{4}\\}$. See Figure 9 for an illustration. Since $G$
is 3-regular, simple and bridgeless, there is a neighbor $b_{i}$ of $a_{i}$
distinct from $\\{a_{0},a_{1},\ldots,a_{4}\\}$, for every $0\leq i\leq 4$. For
example, $b_{0}\neq a_{1}$ by simplicity. If $b_{0}=a_{2}$, i.e., if
$\\{a_{0},a_{2}\\}$ were an edge, then there would be a bridge
$\\{a_{1},b_{1}\\}$. Indeed, the edge $\\{a_{0},a_{2}\\}$ must lie outside of
the pentagon face $P$. If one traverses the edges
$\\{a_{2},a_{1}\\},\\{a_{1},a_{0}\\}$ with $P$ to its left, then follows with
the edge $\\{a_{0},a_{2}\\}$, one gets a cycle which separates the part of $G$
that contains $P$ from the part of $G$ that connects to $a_{1}$ via the edge
$\\{a_{1},b_{1}\\}$ (note that all three neighbors of each vertex in
$\\{a_{0},a_{1},a_{2}\\}$ are accounted for and thus no other adjacent edge
exists to the right of this cycle). So, deleting $\\{a_{1},b_{1}\\}$
disconnects $G$, and thus $\\{a_{1},b_{1}\\}$ is a bridge. Thus,
$b_{0}\not=a_{2}$ as $G$ is bridgeless. See Figure 10 for an illustration. By
symmetry, $b_{0}\neq a_{3},a_{4}$ as well. By the same reason,
$b_{i}\not\in\\{a_{0},a_{1},\ldots,a_{4}\\}$, for all $0\leq i\leq 4$.

$P$$a_{0}$$a_{1}$$a_{2}$$a_{4}$$a_{3}$$b_{1}$ Figure 10: Why $b_{0}\neq a_{2}$

Furthermore, since $G$ has no triangle or square faces and is bridgeless, we
claim that without loss of generality $b_{i}$ are all distinct ($0\leq i\leq
4$). To see that, we first note that $b_{0}\neq b_{1},b_{4}$, for otherwise
there would be a triangle face. Next we deal with the case $b_{0}=b_{2}$ or
$b_{0}=b_{3}$. By symmetry suppose $b_{0}=b_{2}$. There is a third adjacent
vertex $b$ of $b_{0}$, other than $a_{0},a_{2}$. Consider the cycle
$C=(a_{2},a_{1},a_{0},b_{0}=b_{2},a_{2})$ with $P$ to its left, which defines
two simply connected regions in the spherical embedding of $G$. Call the
region that contains $P$ the interior region. If the edge $\\{b_{0},b\\}$ is
in the interior region, then $\\{a_{1},b_{1}\\}$ is a bridge, by the same
proof for $b_{0}\neq a_{2}$. So we may assume $\\{b_{0},b\\}$ lies in the
exterior region of the cycle $C$. (See Figure 11.)

$P$$a_{0}$$a_{1}$$a_{2}$$a_{4}$$a_{3}$$b_{1}$$b_{4}$$b_{3}$$b_{0}=b_{2}$$b$
Figure 11: $\\{b_{0},b\\}$ lies in the exterior region of the cycle $C$

Clearly $b\neq b_{1}$, for otherwise there is a square face. Now there is a
face $\Delta$ bounded by the cycle that contains the edge $\\{a_{1},a_{0}\\}$
on the opposite side of $P$. The bounding cycle contains the path
$(b_{1},a_{1},a_{0},b_{0},b)$, followed by a path
$\pi=(b=x_{0},x_{1},\ldots,x_{\ell}=b_{1})$ of $\ell\geq 1$ edges from $b$
back to $b_{1}$. Here the first edge $\\{b,x_{1}\\}$ is the right branch we
take when we go from $b_{0}$ to $b$, and the last edge
$\\{x_{\ell-1},b_{1}\\}$ is the left branch we take if we go from $a_{1}$ to
$b_{1}$. Similarly there is another face $\Delta^{\prime}$ bounded by the
cycle that contains the edge $\\{a_{1},a_{2}\\}$ on the opposite side of $P$.
The bounding cycle contains the path $b_{1},a_{1},a_{2},b_{0},b$ followed by a
path $\pi^{\prime}$ of $\ell^{\prime}\geq 1$ edges from $b$ back to $b_{1}$.
(See Figure 12.)

$a_{2}$$a_{0}$$a_{1}$$b_{0}=b_{2}$$b$$b_{1}$$e_{1}$$e_{2}$$a_{3}$$a_{4}$$\ell^{\prime}$$\ell$
Figure 12: When $b_{0}=b_{2}$

We will now define two auxiliary graphs $G_{1}$ and $G_{2}$. $G_{1}$ consists
of the cycle $C$ and its interior region, augmented by a single edge
$e^{*}=\\{a_{1},b_{0}\\}$. $G_{2}$ consists of everything in $G$ properly
exterior to the cycle $C$ (i.e., not containing $C$ and its interior) with the
two edges $e_{1}=\\{a_{1},b_{1}\\}$ and $e_{2}=\\{b,b_{0}\\}$ replaced by one
new edge $e_{12}=\\{a_{1},b_{0}\\}$. (See Figure 13). $G_{1}$ is not one of
the exceptional graphs since it contains a pentagon. If $G_{2}$ were $M_{2,3}$
then the two paths $\pi$ and $\pi^{\prime}$ denoted by the dotted lines with
labels $\ell$ and $\ell^{\prime}$ both consist of a single edge and are
present in $G$, contradicting $G$ being simple. If $G_{2}$ were $K_{4}$ then
there are four triangle faces (on the spherical embedding), two of which must
be present in $G$, contradicting $G$ having no triangle faces. So, by
induction, both $G_{1}$ and $G_{2}$ have a P3EM. Note that $G_{1}$ contains
two triangle faces separated by the edge $e^{*}$. Any P3EM of $G_{1}$ assigns
$e^{*}$ to one of these two triangle faces which implies that all three edges
of this triangle face must be assigned to this face. Thus, in Figure 13(a) the
four edges
$\\{a_{1},a_{2}\\},\\{a_{2},b_{0}\\},\\{a_{1},a_{0}\\},\\{a_{0},b_{0}\\}$ must
be assigned all up or all down, according to whether $e^{*}$ is assigned down
or up, respectively. In $G_{2}$, the edge $e_{12}$ is assigned either up or
down to the two adjacent faces. If $e_{12}$ is assigned up, then along the
path $\pi$ (resp. $\pi^{\prime}$) of $\ell$ (resp. $\ell^{\prime}$) edges
there are $0\pmod{3}$ (resp. $2\pmod{3}$) edges assigned toward the face that
$e_{12}$ is on its boundary. If $e_{12}$ is assigned down, then the opposite
happens, i.e., $2\pmod{3}$ (resp. $0\pmod{3}$ ) edges of $\pi$ (resp.
$\pi^{\prime}$) are assigned toward the face that $e_{12}$ is on its boundary.

We now define an edge assignment that will be a P3EM for $G$. Every edge in
$G$ other than $e_{1}$ and $e_{2}$ belongs to exactly one of $G_{1}$ or
$G_{2}$. We assign these edges according to the assignment in $G_{1}$ or
$G_{2}$ respectively. This satisfies the requirement of P3EM for every face
other than $\Delta$ and $\Delta^{\prime}$ in $G$. For the assignment on
$e_{1}$ and $e_{2}$, there are four cases according to how $e^{*}$ in $G_{1}$
and $e_{12}$ in $G_{2}$ are assigned. The first case is both $e^{*}$ in
$G_{1}$ and $e_{12}$ in $G_{2}$ are assign up, and we assign $e_{1}$ down and
$e_{2}$ up in $G$. Then, there are a total of 3 edges
$e_{1}=\\{b_{1},a_{1}\\}$, $\\{a_{1},a_{0}\\}$ and $\\{a_{0},b_{0}\\}$ and
$0\pmod{3}$ edges of $\pi$ assigned toward $\Delta$. Also there are a total of
1 edge $e_{2}=\\{b_{0},b\\}$, and $2\pmod{3}$ edges of $\pi^{\prime}$ assigned
toward $\Delta^{\prime}$. The second case is when $e^{*}$ and $e_{12}$ are
assigned respectively up and down, and we assign $e_{1}$ and $e_{2}$ both down
in $G$. Then, there are a total of 4 edges $e_{1}=\\{b_{1},a_{1}\\}$,
$\\{a_{1},a_{0}\\}$, $\\{a_{0},b_{0}\\}$ and $e_{2}=(b_{0},b)$, and
$2\pmod{3}$ edges of $\pi$ assigned toward $\Delta$, making it $0\pmod{3}$
altogether. Also there are no edge among these four and $0\pmod{3}$ edges of
$\pi^{\prime}$ assigned toward $\Delta^{\prime}$. The other two cases are
similar. We have proved that a P3EM exists for $G$.

Hence we may assume that $b_{0},\ldots,b_{4}$ are all distinct.

$a_{2}$$a_{0}$$a_{1}$$b_{0}=b_{2}$$e^{*}$ (a) $G_{1}$

$b$$b_{1}$$e_{12}$$l^{\prime}$$l$ (b) $G_{2}$

Figure 13: $G_{1}$ and $G_{2}$

We claim that there is a simple path connecting $b_{i}$ and $b_{i+1}$ for each
$0\leq i\leq 4$ (where $b_{5}=b_{0}$), and furthermore the cycle
$(a_{i},b_{i},\ldots,b_{i+1},a_{i+1},a_{i})$ using this path is the boundary
of a face. Define an $a_{i}$-R path as follows: start from $a_{i}$ and take
the first edge $\\{a_{i},b_{i}\\}$, and then at every new vertex (of degree 3)
choose the right branch for the next vertex, until we encounter a previously
visited vertex on this walk, or one of $\\{a_{0},a_{1},\ldots,a_{4}\\}$, then
stop. For notational simplicity we consider the case for $i=0$; all other
cases are the same. Suppose the $a_{0}$-R path is
$\\{x_{0},x_{1},...,x_{k},...,x_{m}\\}$, where $x_{0}=a_{0}$ and
$x_{1}=b_{0}$. First we claim $x_{m}\neq a_{0}$. If it were, then the step
before would have been $a_{1},a_{4}$ or $b_{1}=x_{0}$, but then the $a_{0}$-R
path should have stopped at $x_{m-1}$. Next we claim that
$x_{m}\in\\{a_{1},a_{2},a_{3},a_{4}\\}$. Indeed, if
$x_{m}\not\in\\{a_{1},a_{2},a_{3},a_{4}\\}$, then it is a previously visited
vertex $x_{k}$ on this walk, with $k\geq 1$. Then $x_{k-1}$ exists. Moreover,
$(x_{k},x_{k+1},\dots,x_{m})$ is a cycle which is formed by always taking the
right branch at the next vertex. The last edge $(x_{m-1},x_{m})$ (which is
$(x_{m-1},x_{k})$) must be the left branch edge when coming from the direction
$(x_{k-1},x_{k})$, thus the traversal of the cycle
$(x_{k},x_{k+1},\dots,x_{m})$ is counterclockwise. Thus the edge
$\\{x_{k-1},x_{k}\\}$ is a bridge, a contradiction. See Figure 14 for an
illustration.

$a_{0}=x_{0}$$b_{0}=x_{1}$$x_{2}$$x_{k-1}$$x_{k}=x_{m}$$x_{m-1}$$x_{k+1}$
Figure 14: Simple paths between $b_{i}$’s

Next we claim that $x_{m}=a_{1}$, and $x_{m-1}=b_{1}$, (see Figure 9). We
prove this by eliminating the possibilities $x_{m}\in\\{a_{2},a_{3},a_{4}\\}$.
Suppose $x_{m}=a_{4}$. It follows from the definition of the $a_{0}$-R path
that $x_{m-1}\not\in\\{a_{0},a_{1},\ldots,a_{4}\\}$, being the step before
$x_{m}$, and then the only way to reach $x_{m}=a_{4}$ is $x_{m-1}=b_{4}$.
Since this $a_{0}$-R path always takes the right branch, viewing the plane
graph on a spherical embedding we can consider the face to the right of this
$a_{0}$-R path as the outer face and then the edge $\\{a_{0},a_{4}\\}$ is a
chord. However, by our assumption $G$ is chordless. Now suppose $x_{m}=a_{3}$.
Then consider the $a_{2}$-R path. By planarity and the fact that one single
face borders the right hand side of the $a_{0}$-R path which ends in $a_{3}$,
the $a_{2}$-R path cannot end in $a_{4}$, and therefore it must end in
$a_{1}$. However, considering the indices mod 5 this is exactly the same
situation with the $a_{0}$-R path ending in $a_{4}$, another contradiction.
Finally, if the $a_{0}$-R path ends in $x_{m}=a_{2}$, then the $a_{1}$-R path
would violate planarity, or produce a bridge. We conclude that $x_{m}=a_{1}$.
And then it follows that $x_{m-1}=b_{1}$, and we have a face with boundary
$(a_{0},b_{0},\ldots,b_{1},a_{1},a_{0})$ from this $a_{0}$-R path. The same is
true for all $a_{i}$-R paths.

In other words, we now have a pentagon face $P$ depicted as in Figure 15.

$P$$a_{0}$$a_{1}$$a_{2}$$a_{4}$$a_{3}$$b_{0}$$b_{1}$$b_{2}$$b_{4}$$b_{3}$
Figure 15: Pentagon in the original graph

$a_{0}$$a_{1}$$a_{2}$$a_{4}$$a_{3}$$b_{0}$$b_{1}$$b_{2}$$b_{4}$$b_{3}$$x_{0}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$y_{0}$$y_{1}$$y_{2}$$y_{3}$$y_{4}$$z_{0}$$z_{1}$$z_{4}$$z_{2}$$z_{3}$
(a) pentagon in the original graph

$a_{0}$$a_{4}$$a_{3}$$b_{0}$$b_{1}$$b_{2}$$b_{4}$$b_{3}$$x^{\prime}_{0}$$x^{\prime}_{1}$$x^{\prime}_{2}$$x^{\prime}_{3}$$x^{\prime}_{4}$$y^{\prime}_{3}$$y^{\prime}_{4}$$z^{\prime}_{0}$$z^{\prime}_{1}$$z^{\prime}_{4}$$z^{\prime}_{2}$$z^{\prime}_{3}$
(b) resulting graph

Figure 16: Transforming a pentagon

We now perform the transformation as illustrated in Figure 16. The transformed
graph (b) on the right is not $M_{2,3}$ or $K_{4}$ by vertex count. By
induction there is a P3EM $M^{\prime}$ on the transformed graph. We use
Boolean variables $x^{\prime}_{i}$ ($0\leq i\leq 4$), and $y^{\prime}_{3}$,
$y^{\prime}_{4}$ to denote the assignment on those 7 edges in Figure 16b, such
that the variable is 1 if the corresponding edge is assigned to the face
indicated by its arrow, and is 0 if it is assigned to the face on the other
side. We also use nonnegative integer variables $z^{\prime}_{i}$ ($0\leq i\leq
4$) to denote the number of edges assigned to the side indicated along the
simple path $b_{i}$ to $b_{i+1}$. Now we define a P3EM $M$ on $G$ using
$M^{\prime}$ as follows. All edges in $G$ that are not incident to
$a_{0},a_{1},a_{2},a_{3}$ or $a_{4}$ will retain their assignment as in
$M^{\prime}$. These include all edges on the path $b_{i}$ to $b_{i+1}$ (and
all edges beyond these simple paths that are not depicted in Figure 16a.) In
particular, if $z_{i}$ ($0\leq i\leq 4$) is the number of edges assigned to
the side indicated along the simple path $b_{i}$ to $b_{i+1}$ in $G$, then
$z_{i}=z^{\prime}_{i}$. For the 10 edges incident to at least one of
$a_{0},a_{1},a_{2},a_{3}$ or $a_{4}$ in Figure 16a we will use Boolean
variables $x_{i}$ and $y_{i}$ ($0\leq i\leq 4$) to denote the assignment of
$M$ on $G$, such that the variable is 1 if the corresponding edge is assigned
to the face indicated by its arrow, and is 0 otherwise.

A moment’s reflection will convince the reader that $M$ is a P3EM on $G$ iff
we can assign Boolean 0-1 variables $x_{i}$ and $y_{i}$ ($0\leq i\leq 4$) that
satisfy the following equation system $(\Sigma)$, where
$\overline{x}=1-x\in\\{0,1\\}$ denotes the negation of the Boolean variable
$x$.

$\displaystyle x_{0}+y_{0}+\overline{x_{1}}\equiv
x^{\prime}_{0}+\overline{x^{\prime}_{1}}\pmod{3}$ $\displaystyle
x_{2}+y_{2}+\overline{x_{3}}\equiv
x^{\prime}_{2}+\overline{x^{\prime}_{3}}\pmod{3}$ $\displaystyle
x_{3}+y_{3}+\overline{x_{4}}\equiv
x^{\prime}_{3}+y^{\prime}_{3}+\overline{x^{\prime}_{4}}\pmod{3}$
$\displaystyle x_{4}+y_{4}+\overline{x_{0}}\equiv
x^{\prime}_{4}+y^{\prime}_{4}+\overline{x^{\prime}_{0}}\pmod{3}$
$\displaystyle x_{1}+y_{1}+\overline{x_{2}}\equiv
x^{\prime}_{1}+\overline{x^{\prime}_{2}}+\overline{y^{\prime}_{3}}+\overline{y^{\prime}_{4}}\pmod{3}$
$\displaystyle\sum\limits_{i=0}^{4}\overline{y_{i}}\equiv 0\pmod{3}$

We note that, while this equation system consists of all linear equations mod
3, it is not an ordinary linear equation system over $\mathbb{Z}_{3}$; the
complicating factor is that all the variables must take Boolean values in
$\\{0,1\\}$. Somewhat miraculously, we show that for any Boolean values of
$x^{\prime}_{i}$ ($0\leq i\leq 4$) and $y^{\prime}_{3}$, $y^{\prime}_{4}$, we
can always solve the equation system $(\Sigma)$ for the Boolean variables
$x_{i}$ and $y_{i}$ ($0\leq i\leq 4$).

If $(y^{\prime}_{3},y^{\prime}_{4})\neq(0,0)$, then we set
$x_{i}=x^{\prime}_{i}$ for $0\leq i\leq 4$, $y_{3}=y^{\prime}_{3}$,
$y_{4}=y^{\prime}_{4}$, $y_{0}=y_{2}=0$, and
$y_{1}=\overline{y^{\prime}_{3}}+\overline{y^{\prime}_{4}}\in\\{0,1\\}$. (Note
that $(y^{\prime}_{3},y^{\prime}_{4})\neq(0,0)$ is used to obtain
$\overline{y^{\prime}_{3}}+\overline{y^{\prime}_{4}}\in\\{0,1\\}$.) One can
check that this assignment solves $(\Sigma)$.

Now suppose $(y^{\prime}_{3},y^{\prime}_{4})=(0,0)$. The system of equations
now becomes

$\displaystyle x_{0}+y_{0}+\overline{x_{1}}\equiv
x^{\prime}_{0}+\overline{x^{\prime}_{1}}\pmod{3}$ $\displaystyle
x_{2}+y_{2}+\overline{x_{3}}\equiv
x^{\prime}_{2}+\overline{x^{\prime}_{3}}\pmod{3}$ $\displaystyle
x_{3}+y_{3}+\overline{x_{4}}\equiv
x^{\prime}_{3}+\overline{x^{\prime}_{4}}\pmod{3}$ $\displaystyle
x_{4}+y_{4}+\overline{x_{0}}\equiv
x^{\prime}_{4}+\overline{x^{\prime}_{0}}\pmod{3}$ $\displaystyle
x_{1}+y_{1}+\overline{x_{2}}\equiv
x^{\prime}_{1}+\overline{x^{\prime}_{2}}+2\pmod{3}$
$\displaystyle\sum\limits_{i=0}^{4}\overline{y_{i}}\equiv 0\pmod{3}$

If $x^{\prime}_{1}=0$, then we set $x_{1}=1$, and $x_{i}=x^{\prime}_{i}$ for
$0\leq i\leq 4$, $i\neq 1$, and set $y_{2}=y_{3}=y_{4}=0$, $y_{0}=y_{1}=1$.
One can check that this assignment solves $(\Sigma^{\prime})$. If
$(x^{\prime}_{1},x^{\prime}_{2})=(1,1)$, then we set $x_{2}=0$, and
$x_{i}=x^{\prime}_{i}$ for $0\leq i\leq 4$, $i\neq 2$, and set
$y_{0}=y_{3}=y_{4}=0$, $y_{1}=y_{2}=1$. This solves $(\Sigma^{\prime})$. Thus
it remains to consider the case when $(x^{\prime}_{1},x^{\prime}_{2})=(1,0)$.
There remain eight cases, each corresponding to an assignment
$(x^{\prime}_{0},x^{\prime}_{3},x^{\prime}_{4})\in\\{0,1\\}^{3}$.

At this point we have $(y^{\prime}_{3},y^{\prime}_{4})=(0,0)$ in addition to
$(x^{\prime}_{1},x^{\prime}_{2})=(1,0)$, so now we are in a situation in
Figure 16b where $x^{\prime}_{1},x^{\prime}_{2},y^{\prime}_{3}$ and
$y^{\prime}_{4}$ are all pointing into the face bounded by the cycle
$(b_{1},a_{0},a_{4},a_{3},b_{2},\ldots,b_{1})$. By a reflection along the
$\\{a_{4},b_{4}\\}$-axis, we only need to consider four cases, with
$x^{\prime}_{4}=0$. These four cases are explicitly given in Figure 27, where
we use a double arrow to indicate an actual assignment of the corresponding
edge into the face indicated. For example, the following figure deals with the
case $(x^{\prime}_{0},x^{\prime}_{3},x^{\prime}_{4})=(0,0,0)$.

$x_{0}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$y_{0}$$y_{1}$$y_{2}$$y_{3}$$y_{4}$$x^{\prime}_{0}$$x^{\prime}_{1}$$x^{\prime}_{2}$$x^{\prime}_{3}$$x^{\prime}_{4}$$y^{\prime}_{3}$$y^{\prime}_{4}$
Figure 17: $(x^{\prime}_{0},x^{\prime}_{3},x^{\prime}_{4})=(0,0,0)$

For other cases, see Figure 27.

Finally, we note that the proof is constructive. When smaller graphs are
defined for induction purposes, the size of the smaller graph strictly
decreases and in the case when two smaller graphs are needed (as in the case
dealing with a chord or getting distinct $b_{i}$’s) the sum of sizes of the
smaller graphs is approximately that of the original graph. Tracing through
the proof it can be easily verified that a planar 3-way edge matching can be
found in polynomial time. This completes the proof of Theorem 3.2. ∎

##  4 Dichotomy Theorem

In this section we start the proof of Theorem 2.1. When $\neg(f_{0}=f_{3}=0)$,
(i.e., it is not the case that both $f_{0}=0$ and $f_{1}=0$), by dividing a
nonzero constant and possibly flipping 0 and 1 without changing the complexity
of Holant, we can normalize the signature $[f_{0},f_{1},f_{2},f_{3}]$ to be
$[1,a,b,c]$. We first deal with a special case where $a=b$ and $c=1$.

######  Lemma 4.1.

$\operatorname{Pl-Holant}\left([1,a,a,1]\mid(=_{3})\right)$ is in
$\operatorname{FP}$.

###### Proof.

Perform the holographic transformation by the Hadamard matrix
$H=\left[\begin{smallmatrix}1&1\\\ 1&-1\end{smallmatrix}\right]$, to
$[1,a,a,1]$ on the left and $(=_{3})=[1,0,0,1]$ on the right in the bipartite
setting, we get

$[1,a,a,1]H^{\otimes
3}=[2+6a,0,2-2a,0],~{}~{}~{}\mbox{and}~{}~{}~{}(H^{\otimes
3})^{-1}[1,0,0,1]=\tfrac{1}{4}[1,0,1,0].$

Both transformed signatures are matchgate signatures [CL11] and thus the
problem can be solved in polynomial time by the FKT algorithm. ∎

Another special case where $b=1$ and $a=c$ will be needed later.

######  Lemma 4.2.

$\operatorname{Pl-Holant}\left([1,a,1,a]\mid(=_{3})\right)$ is #P-hard unless
$a=0$ or $\pm 1$, in which cases it is in $\operatorname{FP}$.

(a) Cross-over signature $\mathcal{C}$

(b) Cross-over gadget $G_{4}$

(c) Component $A$

(d) $B=$ Up-Down flipped copy of $A$

Figure 18: Interpolate the cross-over signature $\mathcal{C}$

To prove Lemma 4.2, let us define the cross-over signature $\mathcal{C}$ of
arity 4, illustrated in Figure 18(a). It is 0-1 valued, and it takes value 1
iff the two red dangling edges are equal and the two blue dangling edges are
equal; furthermore, it is a straddled signature where the two top dangling
edges are to be connected to RHS externally and the two bottom dangling edges
are to be connected to LHS externally. In Figure 18(a) only one vertex is
present pictorially. However, when this signature is actually implemented or
interpolated by some construction, the internal vertices that the two top
dangling edges are incident to are LHS vertices; and the internal vertices
that the two bottom dangling edges are incident to are RHS vertices.

For later convenience, we will write the signature matrix for $\mathcal{C}$
with rows (resp. columns) indexed by $(b_{1},b_{2})\in\\{0,1\\}^{2}$
corresponding to the dangling edges on the leftside (resp. rightside) as it
appears in Figure 18(a) (not the LHS, RHS designation according to the
bipartiteness), with $b_{1}$ for the top edge. The signature matrix is
$\mathcal{C}=\left(\begin{smallmatrix}1&0&0&0\\\ 0&0&1&0\\\ 0&1&0&0\\\
0&0&0&1\end{smallmatrix}\right)$. Note that the signature matrix of
$\mathcal{C}$ is invariant under a cyclic rotation by 90∘ of the graph in
Figure 18(a). The importance of this cross-over signature is conveyed in the
following lemma.

We say a signature $f$ can be planarly constructed or interpolated if there is
a polynomial time construction of planar gadgets or a sequence of planar
gadgets with external dangling edges conforming to that of $f$ with respect to
its bipartite specification, such that the construction implements or
interpolates $f$.

######  Lemma 4.3.

For any signature sets $\mathcal{F},\mathcal{G}$, if the cross-over signature
$\mathcal{C}$ can be planarly constructed or interpolated, then
$\operatorname{Holant}\left(\mathcal{F}\mid\mathcal{G}\right)\leq_{T}\operatorname{Pl-
Holant}\left(\mathcal{F}\mid\mathcal{G}\right)$.

###### Proof.

Given any input signature grid of the problem
$\operatorname{Holant}\left(\mathcal{F}\mid\mathcal{G}\right)$, we place it on
the plane with possible edges intersecting each other at non-vertices. We may
assume at most two edges intersect at any point, and the number of such
intersections is polynomially bounded. We replace each such intersection by a
copy of $\mathcal{C}$ as follows. Note that every edge connects a LHS vertex
with a RHS vertex. Suppose an edge $e=\\{u,v\\}$ intersects consecutively
$k\geq 1$ edges at non-vertices $x_{1},\ldots,x_{k}$, where $u$ and $v$ are
from LHS and RHS, respectively. As we traverse from $u$ to $v$, for each
$1\leq i\leq k$ we label R and L respectively just as we enter and leave
$x_{i}$. Labeling in this way for every edge having such intersections, we
find that locally at each intersection point, cyclically two consecutive edges
are labeled R and the other two consecutive edges are labeled L. This is
because at each local intersection point each pair of incident edges that are
_not_ cyclically consecutive are always labeled with distinct R $\neq$ L. A
moment reflection shows that the signature $\mathcal{C}$ can always be used
with a suitable rotation at each intersection, while respecting the bipartite
structure. We thus obtain an input of the problem $\operatorname{Pl-
Holant}\left(\mathcal{F}\mid\mathcal{G}\right)$ with Holant value unchanged. ∎

We are now ready to prove Lemma 4.2.

###### Proof of Lemma 4.2.

When $a=0$ or $\pm 1$, the problem is in the affine class or degenerate,
respectively, and thus in $\operatorname{FP}$ (see [CC17] for details of the
algorithms). Assume $a\neq 0$ and $a\neq\pm 1$. The problem
$\operatorname{Holant}\left([1,a,1,a]\mid(=_{3})\right)$ without the planar
restriction is shown to be #P-hard in [CFL23]. By Lemma 4.3, it suffices to
show we can interpolate the cross-over signature $\mathcal{C}$.

Consider the gadget $G_{4}$ in Figure 18(b) where we place the signature
$[1,a,1,a]$ at the square vertices and $=_{3}$ at the circle vertices. Note
that $G_{4}$ is a straddled signature with the two dangling edges at the top
(reps. bottom) to be connected externally to the RHS (reps. LHS), just like
the cross-over signature $\mathcal{C}$. After normalization by a constant
$a+a^{2}\neq 0$, the signature matrix of $G_{4}$ is
$\left(\begin{smallmatrix}z&1&1&1\\\ 1&1&z&1\\\ 1&z&1&1\\\
1&1&1&z\end{smallmatrix}\right)$, where
$z=\frac{1+a^{3}}{a+a^{2}}=a+a^{-1}-1$. As $a\neq\pm 1$, if $a>0$ then
$z=(a^{1/2}-a^{-1/2})^{2}+1>1$, and if $a<0$ then
$z=-(|a|+|a|^{-1})-1=-(|a|^{1/2}-|a|^{-1/2})^{2}-3<-3$. Here the rows (resp.
columns) are indexed by $(b_{1},b_{2})\in\\{0,1\\}^{2}$ in lexicographic order
corresponding to the dangling edges on the leftside (resp. rightside, as it
appears in Figure 18(b)), with $b_{1}$ for the top edge. This can be verified
by first computing the signatures for $A$ and $B$ in Figures 18(c) and 18(d),
$A=\left(\begin{smallmatrix}1&0&a&0\\\ 0&a&0&1\\\ a&0&1&0\\\
0&1&0&a\end{smallmatrix}\right)$, and $B=\left(\begin{smallmatrix}1&a&0&0\\\
a&1&0&0\\\ 0&0&a&1\\\ 0&0&1&a\end{smallmatrix}\right)$ is obtained from $A$ by
exchanging both middle two rows and middle two columns. Then we have
$G_{4}=A\cdot B\cdot A$, as a matrix product. Notice that the “shape” of
$G_{4}$ looks just like $\mathcal{C}$ if we replace 1 by 0, and $z$ by 1. We
will exploit this remarkable coincidence in our proof below. Note also that
the signature matrix of $G_{4}$ is invariant under cyclic rotations of the
gadget.

Now we define a sequence of gadgets $\Gamma_{2s+1}$ of linear size, which is a
sequential composition of $2s+1$ sub-gadgets, where for odd index
$i=1,3,\ldots,2s+1$ we use $G_{4}$, and for even index $i=2,4,\ldots,2s$ we
use a $180^{\circ}$-rotated copy of $G_{4}$, and we merge the rightside two
edges of the $i$th sub-gadget with the leftside two edges of the $(i+1)$th
sub-gadget. This sequential composition satisfies the bipartite restriction.
As the rotated copy of $G_{4}$ has the same signature matrix as that of
$G_{4}$, the signature matrix of $\Gamma_{2s+1}$ is $G_{4}^{2s+1}$, the
$(2s+1)$th power of $G_{4}$. We can show that it has the form (after
normalization) $\Gamma_{2s+1}=\left(\begin{smallmatrix}x_{s}&1&1&1\\\
1&1&x_{s}&1\\\ 1&x_{s}&1&1\\\ 1&1&1&x_{s}\end{smallmatrix}\right)$, where
$\\{x_{s}\\}_{s\geq 0}$ are defined by a recurrence, with $x_{0}=z$ and

$x_{s+1}=\frac{6+6z+3x_{s}+z^{2}\cdot x_{s}}{7+4z+z^{2}+2x_{s}+2z\cdot
x_{s}}.$

We are going to show that $x_{s}$’s are pairwise distinct. First suppose
$a>0$. We have $x_{s+1}-1=\frac{(z-1)^{2}(x_{s}-1)}{7+4z+z^{2}+2x_{s}+2z\cdot
x_{s}}$, which shows inductively that $x_{s}>1$ for all $s\in\mathbb{N}$, as
the denominator is clearly positive. Next,
$\frac{x_{s+1}-1}{x_{s}-1}=\frac{(z-1)^{2}}{(z+2)^{2}+3+2x_{s}(z+1)}<1$, as
$x_{s},z>1$. It follows that $x_{s+1}<x_{s}$ and hence pairwise distinct. Now
suppose $a<0$. Inductively assume $x_{s}<-3$, which is true at $x_{0}=z<-3$.
We have $x_{s+1}+3=\frac{(z+3)^{2}(x_{s}+3)}{7+4z+z^{2}+2x_{s}+2z\cdot
x_{s}}$. The denominator $7+4z+z^{2}+2x_{s}+2z\cdot
x_{s}=(z+2)^{2}+3+2(z+1)x_{s}>0$, as $z<-3$ and inductively also $x_{s}<-3$.
Then we have $x_{s+1}+3<0$ since $x_{s}+3<0$. Now the denominator is
$(z+2)^{2}+3+2(z+1)x_{s}>|z+2|^{2}>|z+3|^{2}$ as $z<-3$. Hence
$\frac{x_{s+1}+3}{x_{s}+3}=\frac{(z+3)^{2}}{(z+2)^{2}+3+2(z+1)x_{s}}<1$. And
so, $x_{s+1}>x_{s}$, and in particular they are pairwise distinct.

Note also that the number of bits required to represent $x_{s}$’s is
polynomially bounded in the size of the input because $x_{s}$’s come from, by
definition, sums of at most $2^{n^{O(1)}}$ terms, each a product of $n^{O(1)}$
factors.

Given any signature grid $\Omega$ where the cross-over signature $\mathcal{C}$
appears $n$ times, we construct signature grids $\Omega_{s}$, $0\leq s\leq n$,
by replacing each copy of $\mathcal{C}$ by $\Gamma_{2s+1}$ while respecting
the bipartite restrictions. We now stratify the assignments in the Holant sum
for $\Omega$ according to the number $i$, $0\leq i\leq n$, of total times that
the input of $\mathcal{C}$ is (0,0,0,0), (1,0,1,0), (0,1,0,1), or (1,1,1,1) in
cyclic order (these are the only inputs to $\mathcal{C}$ with nonzero
evaluations). Let $c_{i}$ be the sum over all corresponding assignments of the
products from other signatures with this restriction of $i$. Then we have
$\operatorname{Holant}(\Omega)=c_{n}$, and

$\operatorname{Holant}(\Omega_{s})=\sum\limits_{i=0}^{n}x^{i}_{s}\cdot c_{i}.$
(4.1)

Since $x_{s}$’s are pairwise distinct, (4.1) is a full ranked Vandermonde
system, and we can solve for all $c_{i}$ in polynomial time, and in particular
compute $c_{n}$, from the values of $\operatorname{Holant}(\Omega_{s})$,
$0\leq i\leq n$. ∎

Hereafter, we say $[1,a,b,c]$ is #P-hard or in FP to mean the problem
$\operatorname{Pl-Holant}\left([1,a,b,c]\mid(=_{3})\right)$ is #P-hard or in
FP. We shall invoke the following theorem in [KC16] when proving our results:

######  Theorem 4.4 (Kowalczyk & Cai).

Suppose $a,b\in\mathbb{C}$, and let $X=ab$,
$Z=\left(\frac{a^{3}+b^{3}}{2}\right)^{2}$. Then $\operatorname{Pl-
Holant}\left([a,1,b]\mid\left(=_{3}\right)\right)$ is #P-hard except in the
following cases, for which the problem is in $\operatorname{FP}$.

  1. 1.

$X=1$;

  2. 2.

$X=Z=0$;

  3. 3.

$X=-1$ and $Z=0$;

  4. 4.

$X=-1$ and $Z=-1$;

  5. 5.

$X^{3}=Z$.

By restricting Theorem 4.4 to real numbers, we have the following corollary.

######  Corollary 4.5.

Suppose $a,b\in\mathbb{R}$, then $\operatorname{Pl-
Holant}\left([a,1,b]\mid\left(=_{3}\right)\right)$ is #P-hard except in the
following cases, for which the problem is in $\operatorname{FP}$.

  1. 1.

$ab=1$;

  2. 2.

$a=1$ and $b=-1$;

  3. 3.

$a=-1$ and $b=1$;

  4. 4.

$a=b$.

Figure 19: Gadget $G_{1}$

Consider the binary straddled gadget $G_{1}$ in Figure 19. Parallel edges are
allowed. Its signature is $G_{1}=\left[\begin{smallmatrix}1&b\\\
a&c\end{smallmatrix}\right]$, where $G_{1}(i,j)$ (at row $i$ column $j$) is
the value of this gadget when the left dangling edge (from the “square”) and
the right dangling edge (from the “circle” $(=_{3})$) are assigned $i$ and $j$
respectively, for $i,j\in\\{0,1\\}$. Iterating $G_{1}$ sequentially $k$ times
is represented by the matrix power $G_{1}^{k}$. It turns out that it is very
useful either to produce directly or to obtain by interpolation a rank
_deficient_ straddled signature, which would in most cases allow us to obtain
unary signatures on either side. With unary signatures we can connect to a
ternary signature to produce binary signatures on one side and then apply
Corollary 4.5.

The following lemma is proved in [CFL23].

######  Lemma 4.6.

Given the binary straddled signature $G_{1}=\left[\begin{smallmatrix}1&b\\\
a&c\end{smallmatrix}\right]$, we can interpolate the degenerate binary
straddled signature $\left[\begin{smallmatrix}y&xy\\\
1&x\end{smallmatrix}\right]$, provided that $c\neq ab$, $a\neq 0$,
$\Delta=\sqrt{(1-c)^{2}+4ab}\neq 0$ and $\frac{\lambda}{\mu}$ is not a root of
unity, where $\lambda=\frac{-\Delta+(1+c)}{2}$, $\mu=\frac{\Delta+(1+c)}{2}$
are the two eigenvalues, and $x=\frac{\Delta-(1-c)}{2a}$ and
$y=\frac{\Delta+(1-c)}{2a}$.

Given a degenerate binary straddled signature, we want to use it as unary
signatures _in a planar way_. It is only in this step that we need our P3EM
theorem. More concretely, in the next lemma we show how we can _essentially_
separate a binary straddled signature to get a unary signature.

######  Lemma 4.7.

For $\operatorname{Pl-Holant}(\,[1,a,b,c]\,|=_{3})$, $a,b,c\in\mathbb{Q}$,
$a\neq 0$, with the availability of the binary degenerate straddled signature
$\left[\begin{smallmatrix}y&xy\\\ 1&x\end{smallmatrix}\right]$ where
$x=\frac{\Delta-(1-c)}{2a}$, $y=\frac{\Delta+(1-c)}{2a}$ and
$\Delta=\sqrt{(1-c)^{2}+4ab}$, we have the following reductions

  1. 1.

$\operatorname{Pl-Holant}(\,[1+ax,a+bx,b+cx]\,|=_{3})\leq_{T}\operatorname{Pl-
Holant}(\,[1,a,b,c]\,|=_{3})$ except for 2 cases: $[1,a,a,1]$,
$[1,a,-1-2a,2+3a]$;

  2. 2.

$\operatorname{Pl-Holant}(\,[1,a,b,c]\,|[y,0,1])\leq_{T}\operatorname{Pl-
Holant}(\,[1,a,b,c]\,|=_{3})$.

(a) $g_{1}$

(b) $g_{2}$

Figure 20: Two gadgets where each triangle represents the unary gadget $[y,1]$

(a) $f_{1}$

(b) $f_{2}$

(c) $f_{3}$

Figure 21: Three gadgets where each triangle represents the unary gadget
$[1,x]$

###### Proof.

The signature $[1+ax,a+bx,b+cx]$ is the binary signature obtained by
connecting $[1,a,b,c]$ on LHS with $[1,x]$ on RHS. For simplicity, we denote
$f:=[1,a,b,c]$ and $f^{\flat}:=[1+ax,a+bx,b+cx]$.

To prove the first reduction $\operatorname{Pl-
Holant}(\,f^{\flat}\,|=_{3})\leq_{T}\operatorname{Pl-Holant}(\,f\,|=_{3})$,
consider any input instance of the LHS problem. Let $G$ be its underlying 2-3
bipartite plane graph. We may assume $G$ is connected, as the Holant value of
$G$ is the product of the Holant values of its connected components. We can
view $G$ as the edge-vertex incidence graph of a plane 3-regular graph
$G^{\prime}$, where every vertex of degree 2 in $G$ on the LHS is viewed as an
edge in $G^{\prime}$. One can also obtain $G^{\prime}$ by merging the two
edges incident to every vertex of degree 2 in $G$. If $G^{\prime}$ is
isomorphic to one of the two exceptions in Theorem 3.2, then the size of $G$
is constant and we can compute the Holant value directly. Otherwise, we
construct an input of the RHS problem as follows. We first obtain the
degenerate binary straddled signature $D=\left[\begin{smallmatrix}y&xy\\\
1&x\end{smallmatrix}\right]$ in $\operatorname{Pl-
Holant}\left([1,a,b,c]\mid(=_{3})\right)$. Then for every edge of
$G^{\prime}$, which is assigned the binary signature $f^{\flat}$, we replace
it by a copy of $[1,a,b,c]$ and connecting it with the edge of $D$ that
corresponds to $[1,x]$. This leaves 1 dangling edge from each copy of $D$,
each edge functionally equivalent to a unary $[y,1]$ on LHS. They need to be
connected to other $(=_{3})$ signatures in a planar way. Now we apply Theorem
3.2 to the 3-regular plane graph $G^{\prime}$, which constructively assigns
every edge of $G^{\prime}$ one of the two incident faces such that we have a
P3EM. We then add a suitable number of $(=_{3})$ and $f$ in each face and
connect them to _exactly_ 3 copies of $[y,1]$ as shown in Figures 20(a) and
20(b). Theorem 3.2 guarantees that this can be done in a planar way. Each
connection produces a multiplicative factor $g_{1}=y^{3}+1$ in Figure 20(a)
and a multiplicative factor $g_{2}=y^{3}+by^{2}+ay+c$ in Figure 20(b). It can
be directly checked that333We use Mathematica to solve the system of equation
$\begin{cases}g_{1}=y^{3}+1=0\\\ g_{2}=y^{3}+by^{2}+ay+c=0\\\
y=\frac{\Delta+(1-c)}{2a}\end{cases}$ The empty solution of the system is
proved by cylindrical decomposition, an algorithm for Tarski’s theorem on
real-closed fields., for $y=\frac{\Delta+(1-c)}{2a}$, at least one of these
factors is nonzero unless $y=-1$, and in that case the signature has the form
$[1,a,a,1]$ or $[1,a,-2a-1,3a+2]$. The proof of the reduction is complete.

For the reduction $\operatorname{Pl-
Holant}(\,[1,a,b,c]\,|[y,0,1])\leq_{T}\operatorname{Pl-
Holant}(\,[1,a,b,c]\,|=_{3})$, we use the same P3EM argument as above.
Therefore it suffices to “absorb” those dangling unaries $[1,x]$ to produce
some nonzero factor. We claim that at least one of the connection gadgets in
Figures 21(a), 21(b), and 21(c) creates a nonzero global factor. The factors
of these four gadgets are

$\begin{cases}f_{1}=cx^{3}+3bx^{2}+3ax+1\\\
f_{2}=(ab+c)x^{3}+(3bc+2a^{2}+b)x^{2}+(2b^{2}+ac+3a)x+ab+1\\\
\begin{split}f_{3}=&(ab+2abc+c^{3})x^{3}+(2a^{2}+b+2a^{2}c+3ab^{2}+bc+3b^{2}c)x^{2}\\\
&+(3a+3a^{2}b+ac+2b^{2}+2b^{2}c+ac^{2})x+1+2ab+abc\end{split}\end{cases}$

respectively. By setting the three formulae to be 0 simultaneously together
with the condition $x=\frac{\Delta-(1-c)}{2a}$, with $a\neq 0$,
$a,b,c\in\mathbb{Q}$, we found that there is no common solution. The proof is
now complete. ∎

We note that signatures of the form $[3x+y,-x-y,-x+y,3x-y]$ for some $x,y$ are
exactly either of the form $[1,a,-2a-1,3a+2]$ after normalization, or of the
form $[0,a,-2a,3a]$, for some $a$.

######  Remark 1.

Just before Lemma 4.10 we stated that we could _essentially_ separate a binary
straddled signature to get a unary. This statement is delicate. Getting
unrestricted use of the unary $[1,x]$ on RHS would be $\operatorname{Pl-
Holant}\left(f\mid(=_{3}),[1,x]\right)$. The following two problems are
equivalent.

$\operatorname{Pl-
Holant}\left(f,f^{\flat}\mid(=_{3})\right)\equiv_{T}\operatorname{Pl-
Holant}\left(f\mid(=_{3}),[1,x]\right).$

This is because for the second problem, every occurrence of $[1,x]$ is
connected to $f$ to produce $f^{\flat}$, and conversely for the first problem,
every occurrence of $f^{\flat}$ can be replaced by connecting a copy of $f$
with $[1,x]$. However, we do not claim that the problem $\operatorname{Pl-
Holant}\left(f\mid(=_{3}),[1,x]\right)$ is reducible to $\operatorname{Pl-
Holant}\left(f\mid(=_{3})\right)$, which is the following stronger reduction
than what we showed:

$\operatorname{Pl-
Holant}\left(f,f^{\flat}\mid(=_{3})\right)\leq_{T}\operatorname{Pl-
Holant}\left(f\mid(=_{3})\right).$

The issue is that now the input graph for the LHS problem is not an edge-
vertex incidence graph for a 3-regular plane graph, and so we cannot apply
Theorem 3.2 as before. If we merge the two incident edges of all degree 2
vertices (assigned the binary signature $f^{\flat}$) we do get a planar
3-regular graph. But this graph may still have degree 3 vertices labeled $f$,
and not every edge comes from merging a degree 2 vertex that was labeled
$f^{\flat}$. Thus, not every edge participates in a 3-way perfect matching. In
summary, a degenerate binary straddled signature is not completely equivalent
to a unary $[1,x]$ on RHS. We further remark that, if this were true, we would
have a much simpler proof of Theorem 5.2.

######  Remark 2.

Reader should think of Lemma 9 mainly as an illustration of what we will call
the _P3EM argument_. The main take-away is that we can separate a degenerate
binary straddled signature to get unaries so long as we use one of them on
_every_ ternary signature on one side and the remaining dangling unaries can
be absorbed to create a nonzero global factor. For example, in the proof of
Theorem 4.16, we are in fact using the gadget depicted in Figure 24. For the
sake of simplicity for presentation, we will say “interpolate” $[1,x]$ on RHS
or $[y,1]$ on LHS hereafter while the reader is welcome to check the delicate
issue in Remark 1 is taken care.

The following proposition is proved in [CFL23].

######  Proposition 4.8.

For $G_{1}=\left[\begin{smallmatrix}1&b\\\ a&c\end{smallmatrix}\right]$, with
$a,b,c\in\mathbb{Q}$, if it is non-singular (i.e., $c\neq ab$), then it has
two nonzero eigenvalues $\lambda$ and $\mu$. The ratio $\lambda/\mu$ is not a
root of unity _unless_ at least one of the following conditions holds:

$\begin{cases}c+1=0\\\ ab+c^{2}+c+1=0\\\ 2ab+c^{2}+1=0\\\ 3ab+c^{2}-c+1=0\\\
4ab+c^{2}-2c+1=0\\\ \end{cases}$ (4.2)

Figure 22: Binary straddled signature $G_{2}$

Now we introduce a new binary straddled signature $G_{2}$ as shown in Figure
22. The signature matrix of $G_{2}$ is
$\left[\begin{smallmatrix}w&b^{\prime}\\\
a^{\prime}&c^{\prime}\end{smallmatrix}\right]$, where $w=1+ab$,
$a^{\prime}=a+b^{2}$, $b^{\prime}=a^{2}+bc$ and $c^{\prime}=ab+c^{2}$. Similar
to $G_{1}$, we have
$\Delta^{\prime}=\sqrt{(w-c^{\prime})^{2}+4a^{\prime}b^{\prime}}$, two
eigenvalues $\lambda^{\prime}=\frac{-\Delta^{\prime}+(w+c^{\prime})}{2}$ and
$\mu^{\prime}=\frac{\Delta^{\prime}+(w+c^{\prime})}{2}$. If $a^{\prime}\neq
0$, we have $x^{\prime}=\frac{\Delta^{\prime}-(w-c^{\prime})}{2a^{\prime}}$,
$y^{\prime}=\frac{\Delta^{\prime}+(w-c^{\prime})}{2a^{\prime}}$ and if further
$\Delta^{\prime}\neq 0$ we can write its Jordan Normal Form as

$G_{2}=\left(\begin{array}[]{ll}w&b^{\prime}\\\
a^{\prime}&c^{\prime}\end{array}\right)=\left(\begin{array}[]{cc}-x^{\prime}&y^{\prime}\\\
1&1\end{array}\right)\left(\begin{array}[]{ll}\lambda^{\prime}&0\\\
0&\mu^{\prime}\end{array}\right)\left(\begin{array}[]{cc}-x^{\prime}&y^{\prime}\\\
1&1\end{array}\right)^{-1}.$ (4.3)

Similar to Proposition 4.8, we have the following claim on $G_{2}$.

######  Proposition 4.9.

If the signature matrix of $G_{2}$ is non-degenerate, then the ratio
$\lambda^{\prime}/\mu^{\prime}$ of its eigenvalues is not a root of unity
_unless_ at least one of the following conditions holds, where
$A=w+c^{\prime},B=(c^{\prime}-w)^{2}+4a^{\prime}b^{\prime}$.

$\begin{cases}A=0\\\ B=0\\\ A^{2}+B=0\\\ A^{2}+3B=0\\\ 3A^{2}+B=0\\\
\end{cases}$ (4.4)

######  Lemma 4.10.

Suppose $a,b,c\in\mathbb{Q}$, $a\neq 0$ and $c\neq ab$ and $a,b,c$ do not
satisfy any condition in (4.2). Let $x=\frac{\Delta-(1-c)}{2a}$,
$y=\frac{\Delta+(1-c)}{2a}$ and $\Delta=\sqrt{(1-c)^{2}+4ab}$. Then for
$\operatorname{Holant}(\,[1,a,b,c]\,|=_{3})$,

  1. 1.

we can interpolate $[y,1]$ on LHS;

  2. 2.

we can interpolate $[1,x]$ on RHS except for 2 cases: $[1,a,a,1]$,
$[1,a,-1-2a,2+3a]$.

###### Proof.

This lemma follows from Lemma 4.6 and Lemma 4.7 using the binary straddled
gadget $G_{1}$ with signature matrix $\left[\begin{smallmatrix}1&b\\\
a&c\end{smallmatrix}\right]$. Note that $c\neq ab$ indicates that matrix
$G_{1}$ is non-degenerate, and $\lambda/\mu$ not being a root of unity is
equivalent to none of the equations in (4.2) holds. ∎

We have similar statements corresponding to $G_{2}$. When the signature matrix
is non-degenerate and does not satisfy any condition in (4.4), we can
interpolate the corresponding $[y^{\prime},1]$ on LHS, and we can also
interpolate the corresponding $[1,x^{\prime}]$ on RHS except when
$y^{\prime}=-1$.

######  Definition 4.11.

For $\operatorname{Pl-Holant}(\,[1,a,b,c]\,|=_{3})$, with
$a,b,c\in\mathbb{Q}$, $a\neq 0$, we say a binary straddled gadget $G$ _works_
if the signature matrix of $G$ is non-degenerate and the ratio of its two
eigenvalues $\lambda/\mu$ is not a root of unity.

######  Remark 3.

Explicitly, the condition that $G_{1}$ _works_ is that $c\neq ab$ and $a,b,c$
do not satisfy any condition in (4.2), which is just the assumptions in Lemma
4.10. $G_{1}$ _works_ implies that it can be used to interpolate $[y,1]$ on
LHS, and to interpolate $[1,x]$ on RHS with two exceptions for which we
already proved the dichotomy. The $x,y$ are as stated in Lemma 4.10.

Similarly, when the binary straddled gadget $G_{2}$ _works_ , for the
corresponding values $x^{\prime}$ and $y^{\prime}$, we can interpolate
$[y^{\prime},1]$ on LHS, and we can interpolate $[1,x^{\prime}]$ on RHS except
when $y^{\prime}=-1$.

Figure 23: A ternary gadget $G_{3}$

The ternary gadget $G_{3}$ in Figure 23 will be used in the proof here and
later.

The unary signatures $\Delta_{0}=[1,0]$ and $\Delta_{1}=[0,1]$ are called the
pinning signatures because they “pin” a variable to 0 or 1. Another useful
unary signature is $\Delta_{2}=[1,1]$. One good use of having unary signatures
is that we can use Lemma 4.13 to get these three signatures. They are helpful
as the following lemma shows.

######  Lemma 4.12.

If $\Delta_{0}$, $\Delta_{1}$ and $\Delta_{2}$ can be interpolated on the RHS
in $\operatorname{Pl-Holant}(\,[1,a,b,c]\,|=_{3})$, where
$a,b,c\in\mathbb{Q}$, $ab\neq 0$, then the problem is #P-hard unless
$[1,a,b,c]$ is affine or degenerate, in which cases it is in FP.

###### Proof.

Connecting $[1,0]$, $[0,1]$ to $[1,a,b,c]$ on LHS respectively, we get binary
signatures $[1,a,b]$ and $[a,b,c]$. Then we can apply Corollary 4.5, and the
problem is #P-hard unless both $[1,a,b]$ and $[a,b,c]$ are in FP. When $ab\neq
0$, both $[1,a,b]$ and $[a,b,c]$ are in FP only when $[1,a,b,c]$ is (1)
degenerate, i.e. $b=a^{2}$ and $c=a^{3}$, in which case the problem is in FP,
(2) of the form $[1,a,1,a]$ which is resolved by Lemma 4.2 (when $a=\pm 1$,
$[1,a,1,a]$ is degenerate), (3) of the form $[1,a,a^{2},a]$ which we will
resolve later in this proof, (4) $[1,a,b,c]=[1,1,1,-1]$ or $[1,-1,1,1]$ which
we will resolve later in this proof, or (5) $[1,a,b,c]=[1,1,-1,-1]$ or
$[1,-1,-1,1]$ which are affine and hence in FP.

For case (2), if we connect $[1,1]$ to $[1,a,a^{2},a]$, we get a binary
signature $[1+a,a+a^{2},a+a^{2}]$ which after normalization (when $a\neq-1$)
is $[1,a,a]$. This problem is #P-hard by Corollary 4.5 unless $a=\pm 1$, in
which cases the problem $[1,a,b,c]$ is $[1,1,1,1]$ or $[1,-1,1,-1]$ which are
degenerate and thus in FP.

For case (3), due to the symmetry by flipping 0 and 1 in the signature, it
suffices to consider only $f=[1,1,1,-1]$ and $g=[1,-1,1,1]$; they are neither
affine nor degenerate. For both $f$ and $g$ we use the gadget $G_{3}$ to
produce ternary signatures $f^{\prime}=[1,1,3,3]$ and $g^{\prime}=[1,1,-1,3]$
respectively. Neither are among the exceptional cases above. So
$\operatorname{Holant}(\,f\,|=_{3})$ and $\operatorname{Holant}(\,g\,|=_{3})$
are both #P-hard. ∎

The following lemma lets us interpolate arbitrary unary signatures on RHS, in
particular $\Delta_{0}$, $\Delta_{1}$ and $\Delta_{2}$, from a binary gadget
with a straddled signature and a suitable unary signature $s$ on RHS.

######  Lemma 4.13 (Vadhan, [Vad01]).

Let $M\in\mathbb{R}^{2\times 2}$ be a non-singular signature matrix for a
binary straddled gadget which is diagonalizable with distinct eigenvalues, and
$s=[a,b]$ be a unary signature on RHS that is not a row eigenvector of $M$.
Then $\\{s\cdot M^{j}\\}_{j\geq 0}$ can be used to interpolate any unary
signature on RHS.

###  4.1 Dichotomy for $[1,a,b,c]$ when $ab\neq 0$ and $G_{1}$ works

Figure 24: Non-linearity gadget, where a triangle represents the unary gadget
$[y,1]$

Let us introduce a _non-linearity_ gadget in Figure 24. If we place in the
non-linearity gadget the binary degenerate straddled signature $D$ on
triangles (in the way that respects the bipartite structure), $f$ on squares
and $(=_{3})$ on circles, we get its signature
$[1,x]\otimes[1,x]\otimes[y^{2}+yb,ya+c]$. Note that it is a ternary planar
gadget on RHS. The following two lemmas will be used in the proof of Theorem
4.16.

######  Lemma 4.14.

Let $a,b,c\in\mathbb{Q}$, $ab\neq 0$, and satisfy
_(con1)_ $a^{3}-b^{3}-ab(1-c)=0$ and
_(con2)_ $a^{3}+ab+2b^{3}=0$.
Then $\operatorname{Pl-Holant}(\,[1,a,b,c]\,|=_{3})$ is #P-hard unless it is
$[1,-1,1,-1]=[1,-1]^{\otimes 3}$ which is degenerate, or a matchgate, in both
cases the problem is in FP.

###### Proof.

If $a+b^{2}=0$ in addition to (_con1_) and (_con2_) with $ab\neq 0$, then
$[1,a,b,c]=[1,-1,1,-1]$ which is degenerate. Now we assume $a+b^{2}\neq 0$.
Here we use Gadget $G_{2}$.

First assume $G_{2}$ _works_. Using $a+b^{2}\neq 0$ together with (_con1_) and
(_con2_), we can verify that
$\Delta=\sqrt{4(a+b^{2})(a^{2}+bc)+(c^{2}-1)^{2}}\not=0$, and we can write the
Jordan Normal Form

$G_{2}=\left(\begin{array}[]{ll}1+ab&a^{2}+bc\\\
a+b^{2}&ab+c^{2}\end{array}\right)=\left(\begin{array}[]{cc}-x&y\\\
1&1\end{array}\right)\left(\begin{array}[]{ll}\lambda&0\\\
0&\mu\end{array}\right)\left(\begin{array}[]{cc}-x&y\\\
1&1\end{array}\right)^{-1},$

where $\lambda=\frac{1+2ab+c^{2}-\Delta}{2}$,
$\mu=\frac{1+2ab+c^{2}+\Delta}{2}$, $x=\frac{\Delta+c^{2}-1}{2(a+b^{2})}$,
$y=\frac{\Delta-c^{2}+1}{2(a+b^{2})}$. Because $G_{2}$ works, $[y,1]$ on LHS
is available. Use this $[y,1]$ in the non-linearity gadget in Figure 24, we
get the unary signature $\left[y^{2}+yb,ya+c\right]$ on the RHS. By Lemma
4.13, we can interpolate any unary signature, in particular $\Delta_{0}$,
$\Delta_{1}$ and $\Delta_{2}$ on RHS and apply Lemma 4.12, unless
$\left[y^{2}+yb,ya+c\right]$ is proportional to a row eigenvector of $G_{3}$,
namely $[1,-y]$ and $[1,x]$. Thus the exceptions are $ya+c=x(y^{2}+yb)$ and
$ya+c=-y(y^{2}+yb)$. Notice that now $xy=\frac{a^{2}+bc}{a+b^{2}}$. The first
equation implies $c=ab$ or $a+b^{2}=0$ or $a^{3}-b^{3}c+ab(-1+c^{2})=0$. The
second equation implies $a+b^{2}=0$ or $f_{1}=0$ where
$f_{1}=a^{3}+4a^{6}+3a^{5}b^{2}+a^{3}b^{3}-c-4a^{3}c+6a^{4}bc-6a^{2}b^{2}c-b^{3}c-3a^{2}b^{5}c-3a^{3}c^{2}-3abc^{2}-4b^{3}c2-a^{3}b^{3}c^{2}-6ab^{4}c^{2}-4b^{6}c^{2}+3c^{3}+4a^{3}c^{3}+6a^{2}b^{2}c^{3}+3b^{3}c^{3}+a^{3}c^{4}+3abc^{4}+4b^{3}c^{4}-3c^{5}-b^{3}c^{5}+c^{7}$.
So there are four exceptional cases,

$\begin{cases}c=ab\\\ a+b^{2}=0\\\ a^{3}-b^{3}c+ab(-1+c^{2})=0\\\ f_{1}=0\\\
\end{cases}$ (4.5)

For each of them, together with (_con1_) and (_con2_), we get 3 equations and
can solve them using Mathematica™. For rational $a,b,c$, when $ab\neq 0$,
there are only two possible results — $[1,-1,1,-1]$ and
$[1,-\frac{1}{3},-\frac{1}{3},1]$. The first one violates $a+b^{2}\neq 0$, and
the second is a matchgate and thus in $\operatorname{FP}$. For all other cases
when $G_{2}$ works, we have the pinnng signatures $\Delta_{0}$, $\Delta_{1}$
and $\Delta_{2}$ on the RHS and then the lemma is proved by Lemma 4.12.

Now suppose $G_{2}$ does not work. Then by Proposition 4.9, we get at least
one more condition, either one in (4.4) or
$(a+b^{2})(a^{2}+bc)=(1+ab)(ab+c^{2})$ which indicates that $G_{2}$ is
degenerate. For each of the 6 conditions, together with (_con1_) and (_con2_),
we can solve them using Mathematica™ for rational $a,b,c$. The only solution
is $[1,-1,1,-1]$ which violates $a+b^{2}\neq 0$. The proof of the lemma is
complete. ∎

######  Lemma 4.15.

Let $a,b,c\in\mathbb{Q}$, $ab\neq 0$, and satisfy
_(con1)_ $a^{3}-b^{3}-ab(1-c)=0$ and
_(con2)_ $(a^{4}b+ab^{4})^{2}=(a^{5}+b^{4})(b^{5}+a^{4}c)$.
Then $\operatorname{Pl-Holant}(\,[1,a,b,c]\,|=_{3})$ is #P-hard unless it is
$[1,a,a^{2},a^{3}]$ which is degenerate, or a matchgate, in both cases the
problem is in FP.

###### Proof.

Eliminating $c$ from (_con1_) and (_con2_) we get
$a^{11}-a^{9}b+a^{6}b^{4}+a^{5}b^{6}-a^{4}b^{5}-a^{3}b^{7}+a^{2}b^{9}-b^{10}=0$,
which, quite miraculously, can be factored as
$(a^{2}-b)(a^{9}+a^{4}b^{4}+a^{3}b^{6}+b^{9})=0$. If $b=a^{2}$, then with
(_con1_), we get $c=a^{3}$ thus the signature becomes $[1,a,a^{2},a^{3}]$
which is degenerate. We assume $a^{9}+a^{4}b^{4}+a^{3}b^{6}+b^{9}=0$, then the
rest of the proof is essentially the same as Lemma 4.14. ∎

######  Theorem 4.16.

For $a,b,c\in\mathbb{Q}$, $ab\neq 0$, if $G_{1}$ works, then
$\operatorname{Pl-Holant}([1,a,b,c]|=_{3})$ is #P-hard unless it is in the
tractable cases of Theorem 2.1 and thus in FP.

###### Proof.

If $[1,a,b,c]$ has the form $[1,a,a,1]$ or $[1,a,-1-2a,2+3a]$ then the problem
is in FP. We now assume the signature is not of these two forms. By Lemma
4.10, when $G_{1}$ works, we can interpolate $[y,1]$ on LHS and also $[1,x]$
on RHS.

Let us write down the Jordan Normal Form again:

$G_{1}=\left(\begin{array}[]{ll}1&b\\\
a&c\end{array}\right)=\left(\begin{array}[]{cc}-x&y\\\
1&1\end{array}\right)\left(\begin{array}[]{ll}\lambda&0\\\
0&\mu\end{array}\right)\left(\begin{array}[]{cc}-x&y\\\
1&1\end{array}\right)^{-1},$

$\lambda=\frac{-\Delta+(1+c)}{2}$, $\mu=\frac{\Delta+(1+c)}{2}$,
$x=\frac{\Delta-(1-c)}{2a}$, $y=\frac{\Delta+(1-c)}{2a}$,
$\Delta=\sqrt{(1-c)^{2}+4ab}$.

Using $[y,1]$ and the gadget in Figure 24, we get $\left[y^{2}+yb,ya+c\right]$
on the RHS. We can interpolate $\Delta_{0}$, $\Delta_{1}$ and $\Delta_{2}$ on
RHS unless $\left[y^{2}+yb,ya+c\right]$ is proportional to a row eigenvector
of $G_{1}$, namely $[1,-y]$ or $[1,x]$, according to Lemma 4.13. Thus the
exceptions are $ya+c=(y^{2}+yb)x$ or $ya+c=-y(y^{2}+yb)$. The first equation
implies $a^{3}-b^{3}-ab(1-c)=0$ or $c=ab$. The second equation implies $c=ab$
or $c=1+a-b$.

By assumption $G_{1}$ works, so $c\neq ab$. Thus, we consider two exceptional
cases.

Case 1: $a^{3}-b^{3}-ab(1-c)=0$

In this case, we have $1-c=\frac{a^{3}-b^{3}}{ab}$ and thus
$\Delta=\sqrt{(1-c)^{2}+4ab}=|\frac{a^{3}+b^{3}}{ab}|$. One condition
($4ab+c^{2}-2c+1=0$) in (4.2) is the same as $\Delta=0$. Since $G_{1}$ works,
we have $\Delta\neq 0$ and thus $a^{3}+b^{3}\neq 0$, which is equivalent to
$a+b\neq 0$ when $a,b\in\mathbb{Q}$.

Subcase 1: $\frac{a^{3}+b^{3}}{ab}>0$. We have
$[1,x]=[1,\frac{\Delta-\left(1-c\right)}{2a}]=[1,\frac{b^{2}}{a^{2}}]$ on RHS.
Connect $[1,x]$ to $[1,a,b,c]$ on LHS, we get the binary signature
$[1+\frac{b^{2}}{a},a+\frac{b^{3}}{a^{2}},b+\frac{b^{2}c}{a^{2}}]$ on LHS.
Note that $a+\frac{b^{3}}{a^{2}}\neq 0$ when $a+b\neq 0$. It is #P-hard (and
thus the problem $[1,a,b,c]$ is #P-hard) unless one of the tractable
conditions in Corollary 4.5 holds. It turns out that the only possibilities
are either (1) first case in Corollary 4.5, i.e.
$(1+\frac{b^{2}}{a})(b+\frac{b^{2}c}{a^{2}})=(a+\frac{b^{3}}{a^{2}})^{2}$,
which becomes $\left(a^{2}-b\right)\left(a^{3}+ab+2b^{3}\right)=0$ after
substituting $c=\frac{ab-a^{3}+b^{3}}{ab}$, or (2) the second and third case
in Corollary 4.5, which implies $(a=-b^{2})\wedge(c=-b^{3})$ and thus the
problem $[1,a,b,c]$ becomes the problem $[1,-b^{2},b,-b^{3}]$, or (3) the
fourth case in Corollary 4.5, which implies $(a=b)\wedge(c=1)$ or
$(a=-b^{2})\wedge(c=-b^{3})$, where in the former case $[1,a,b,c]$ is of the
matchgate form $[1,a,a,1]$ and thus in FP.

We now deal with the case (1). When $a^{2}-b=0$, together with
$a^{3}-b^{3}=ab\left(1-c\right)$, we have $c=a^{3}$, and thus $[1,a,b,c]$ is
degenerate. When $a^{3}+ab+2b^{3}=0$, together with
$a^{3}-b^{3}=ab\left(1-c\right)$, by Lemma 4.14, $[1,a,b,c]$ is #P-hard (with
$a+b\neq 0$ ruling out the exception).

We now deal with the case $[1,-b^{2},b,-b^{3}]$. If $b=0,\pm 1$, it is
degenerate or affine. Now assume $b\neq 0,\pm 1$.
$G_{1}=\left[\begin{smallmatrix}1&b\\\
-b^{2}&b^{3}\end{smallmatrix}\right]=\left[\begin{smallmatrix}1\\\
-b^{2}\end{smallmatrix}\right]\cdot\left[\begin{smallmatrix}1&b\end{smallmatrix}\right]$.
Then we can get $[1,-b^{2}]$ on the LHS. Note that connecting three copies of
$[1,b]$ with $[1,-b^{2},b,-b^{3}]$ on LHS produces a global factor
$1-b^{6}\neq 0$. Connect $[1,-b^{2}]$ twice to $[1,0,0,1]$ on RHS, and we get
$[1,b^{4}]$ on RHS. Connect $[1,b^{4}]$ back to $[1,-b^{2},b,-b^{3}]$ on LHS,
and we get a binary signature $g=[1-b^{6},-b^{2}+b^{5},b-b^{7}]$, which by
Corollary 4.5 is #P-hard unless $b=\pm 1$ which has been discussed, and
therefore $[1,-b^{2},b,-b^{3}]$ is also #P-hard.

Subcase 2: $\frac{a^{3}+b^{3}}{ab}<0$. We have
$[y,1]=[-\frac{b^{2}}{a^{2}},1]$ on LHS. Connecting two copies of $[y,1]$ to
$(=_{3})$ we get $[y^{2},1]=[\frac{b^{4}}{a^{4}},1]$ on RHS. Connecting it
back to LHS, we get a binary signature
$[\frac{b^{4}}{a^{4}}+a,\frac{b^{4}}{a^{3}}+b,\frac{b^{5}}{a^{4}}+c]$ on LHS.
It is #P-hard unless one of the tractable conditions in Corollary 4.5 holds.
It turns out that the only possibilities are either
$(a^{4}b+ab^{4})^{2}=(a^{5}+b^{4})(b^{5}+a^{4}c)$, or $(a=b)\wedge(c=1)$ which
is the matchgate case and thus in FP. We now deal with the former case.
Together with $a^{3}-b^{3}=ab\left(1-c\right)$, by Lemma 4.15, $[1,a,b,c]$ is
#P-hard unless it is degenerate.

Case 2: $1+a-b-c=0$

In this case, $\Delta=|a+b|$, and since $G_{1}$ works, one condition is
$4ab+c^{2}-2c+1=0$ in (4.2) which says $\Delta\neq 0$, and thus $a+b\neq 0$.

If $a+b>0$, then $\Delta=a+b$, and $x=\frac{a+b-(1-c)}{2a}=1$. Then we can
interpolate $[1,x]=[1,1]$ on RHS (as
$y=\frac{a+b+(1-c)}{2a}=\frac{b}{a}\neq-1$). Else, $a+b<0$, then
$\Delta=-(a+b)$, and $y=\frac{-a-b+(1-c)}{2a}=\frac{-a-b+(b-a)}{2a}=-1$. We
can get $[1,1]$ on RHS by connecting two copies of $[y,1]=[-1,1]$ to
$[1,0,0,1]$. Then connecting $[1,1]$ to $[1,a,b,c]$ on LHS we get a binary
signature $[a+1,a+b,a+c]$ on LHS. Again we can apply Corollary 4.5 to it, and
conclude that it is #P-hard. It turns out that the only feasible cases of
tractability leads to $[1,a,-1-2a,2+3a]$, and $(c=1)\wedge(a=b)$, in both
cases the problem is in FP. This proves the #P-hardness of
$\operatorname{Holant}(\,[1,a,b,c]\,|=_{3})$. ∎

###  4.2 Dichotomy for $[1,a,b,0]$

######  Theorem 4.17.

The problem $[1,a,b,0]$ for $a,b\in\mathbb{Q}$ is #P-hard unless it is in the
tractable cases of Theorem 2.1 and thus in FP.

###### Proof.

If $ab\neq 0$ and $G_{1}$ works, then this is proved in Theorem 4.16. If
$a=b=0$, it is degenerate and in FP. We divide the rest into three cases:

  1. 1.

$ab\neq 0$ and $G_{1}$ does not work;

  2. 2.

$f=[1,a,0,0]$ with $a\neq 0$;

  3. 3.

$f=[1,0,b,0]$ with $b\neq 0$.

$\bullet$ Case 1: $ab\neq 0$ in $f=[1,a,b,0]$ and $G_{1}$ does not work. Since
$c=0\neq ab$, this implies that at least one equation in (4.2) holds. After a
simple derivation, we have the following family of signatures to consider:
$[1,a,-\frac{1}{ka},0]$, for $k=1,2,3,4$.

We use $G_{3}$ to produce another symmetric ternary signature in each case. If
the new signature is #P-hard, then so is the given signature. We will describe
the case $[1,a,-\frac{1}{a},0]$ in more detail; the other three types
($k=2,3,4$) are similar.

For $k=1$, the gadget $G_{3}$ produces
$g=[3a^{3}+4,a^{4}-a-\frac{2}{a^{2}},-a^{2}+\frac{1}{a}+\frac{1}{a^{4}},a^{3}+3]$.
For $a=-1$, this is $[1,0,-1,2]$, which has the form
$[1,a^{\prime},-1-2a^{\prime},2+3a^{\prime}]$ and is in FP. Below we assume
$a\not=-1$. Then all entries of $g$ are nonzero.

We claim that the gadget $G_{1}$ works using $g$. Since $a\in\mathbb{Q}$, it
can be checked that $g$ is non-degenerate since
$(a^{4}-a-\frac{2}{a^{2}})(-a^{2}+\frac{1}{a}+\frac{1}{a^{4}})=(3a^{3}+4)(a^{3}+3)$
has no solution, and that no equation in (4.2) has a solution applied to $g$.
Hence, $G_{1}$ works using $g$ and we may apply Theorem 4.16 to $g$. Using the
fact that $a\in\mathbb{Q}$, one can show that $g$ cannot be a Gen-Eq because
it has no zero entry, nor can it be affine or degenerate. Also, it can be
checked that there is no solution for $a$ if we were to impose the condition
that $g$ is a matchgate, i.e.
$(3a^{3}+4=a^{3}+3)\wedge(a^{4}-a-\frac{2}{a^{2}}=-a^{2}+\frac{1}{a}+\frac{1}{a^{4}})$,
and also $a=-1$ is the only solution for $g$ being in the form
$[1,a^{\prime},-1-2a^{\prime},2+3a^{\prime}]$. Thus $[1,a,-\frac{1}{a},0]$ is
#P-hard.

$\bullet$ Case 2: $f=[1,a,0,0]$ with $a\neq 0$. The gadget $G_{3}$ produces
$g^{\prime}=[3a^{3}+1,a^{4}+a,a^{2},a^{3}]$. Since $a\in\mathbb{Q}$,
$3a^{3}+1\neq 0$. If $a=-1$, $g^{\prime}=[-2,0,1,-1]$ and it suffices to
consider $[1,-1,0,2]$ (which is $-1$ times the reversal $[-1,1,0,-2]$ obtained
by swapping and roles of 0 and 1), in which case $G_{2}$ works where the
matrix $G_{2}=\left[\begin{smallmatrix}1&1\\\ -1&4\end{smallmatrix}\right]$.
We can interpolate $[1,x]=[1,-\frac{3+\sqrt{5}}{2}]$ on RHS. Connect it back
to $[1,-1,0,2]$ and get a binary signature
$[\frac{5+\sqrt{5}}{2},-1,-(3+\sqrt{5})]$ on LHS, which, by Corollary 4.5, is
#P-hard. Thus, $[1,-1,0,2]$ is #P-hard and so is $[1,a,0,0]$.

Else, $a\neq-1$. We claim that the gadget $G_{1}$ works using $g^{\prime}$.
The signature $g^{\prime}$ is non-degenerate since $a\in\mathbb{Q}$ is nonzero
and thus $(a^{4}+a)a^{2}\not=(3a^{3}+1)a^{3}$. Also no equation in (4.2) has a
solution applied to $g^{\prime}$. Hence, $G_{1}$ works using $g^{\prime}$ and
we may apply Theorem 4.16 to $g^{\prime}$. Using the fact that
$a\in\mathbb{Q}$, one can show that $g^{\prime}$ cannot be a Gen-Eq because it
has no zero entry, nor can it be affine or degenerate. Also, there is no
solution for $g^{\prime}$ being a matchgate or in the form
$[1,a^{\prime},-1-2a^{\prime},2+3a^{\prime}]$. Thus $[1,a,0,0]$ is #P-hard.

$\bullet$ Case 3: $f=[1,0,b,0]$ with $b\neq 0$. The gadget $G_{1}$ produces a
binary straddled signature $G_{1}=\left[\begin{smallmatrix}1&b\\\
0&0\end{smallmatrix}\right]=\left[\begin{smallmatrix}1\\\
0\end{smallmatrix}\right]\cdot\left[\begin{smallmatrix}1&b\end{smallmatrix}\right]$
which decomposes into a unary signature $[1,b]$ on RHS and a unary signature
$[1,0]$ on LHS. This gives us a reduction $\operatorname{Pl-
Holant}([1,b^{2},b]|(=_{3}))\leq_{T}\operatorname{Pl-Holant}(\,f\,|=_{3})$ by
the P3EM argument. The problem $\operatorname{Pl-Holant}([1,b^{2},b]|=_{3})$
is #P-hard except $b=\pm 1$, by Corollary 4.5, which implies that
$\operatorname{Pl-Holant}(\,f\,|=_{3})$ is also #P-hard when $b\neq\pm 1$. If
$b=\pm 1$, then $f$ is affine, and $\operatorname{Pl-Holant}(\,f\,|=_{3})$ is
in FP. ∎

###  4.3 Dichotomy for $[1,a,0,c]$

######  Theorem 4.18.

The problem $[1,a,0,c]$ with $a,c\in\mathbb{Q}$ is #P-hard unless $a=0$, in
which case it is Gen-Eq and thus in FP.

###### Proof.

When $a=0$, it is Gen-Eq and so is in FP. When $a\neq 0$, if $c=0$, it is
#P-hard by Theorem 4.17. In the following we discuss $[1,a,0,c]$ with $ac\neq
0$.

If $c=\pm 1$, the signature is $[1,a,0,1]$ or $[1,a,0,-1]$. We use $G_{2}$ to
produce a ternary signature $g=[3a^{3}+1,a^{4}+a,a^{2},a^{3}+1]$ (both mapped
to the same signature, surprisingly). If $a=-1$, it is $[1,0,-\frac{1}{2},0]$
after normalization, which by Theorem 4.17 is #P-hard and so is the given
signature $[1,-1,0,1]$. If $a\neq-1$, then $g$ has no zero entry. We then
claim that the gadget $G_{1}$ works using $g$. It can be checked that $g$ is
non-degenerate since $(a^{4}+a)a^{2}=(3a^{3}+1)(a^{3}+1)$ has no solution, and
that no equation in (4.2) has a solution applied to $g$. Hence, $G_{1}$ works
using $g$ and we may apply Theorem 4.16 to $g$. Using the fact that
$a\in\mathbb{Q}$, one can show that $g$ cannot be a Gen-Eq because it has no
zero entry, nor can it be affine or degenerate. Also, it can be checked that
the only solution for $a$ if we were to impose the condition that $g$ is a
matchgate or in the form $[1,a^{\prime},-1-2a^{\prime},2+3a^{\prime}]$ for
some $a^{\prime}$ is $a=0$. Thus $[1,a,0,\pm 1]$ are both #P-hard.

Now assume $c\neq 0,\pm 1$. We claim that the gadget $G_{1}$ works. It can be
checked that for the non-degenerate matrix
$G_{1}=\left[\begin{smallmatrix}1&0\\\ a&c\end{smallmatrix}\right]$,
$\Delta=|1-c|$, $\lambda/\mu\in\\{c,\frac{1}{c}\\}$ is not a root of unity.
Next we claim that we can obtain $[1,0]$ on RHS. If $c<1$ by Lemma 4.10 we can
interpolate $[1,x]=[1,0]$ on RHS with two exceptions to which we already give
a dichotomy (see the Remark after Definition 4.11). If $c>1$, we can
interpolate $[y,1]=[0,1]$ on LHS and so the gadget in Figure 24 produces
$[0,c]$ on RHS, which is not proportional to the row eigenvectors
$[1,-y]=[1,0]$ and $[1,x]=[1,\frac{c-1}{a}]$ of $G_{1}$. By Lemma 4.13, we can
interpolate any unary gadget on RHS, including $[1,0]$. Thus we can always get
$[1,0]$ on RHS. Connect $[1,0]$ to $[1,a,0,c]$ and we will get a binary
signature $[1,a,0]$ on LHS, which is #P-hard by Corollary 4.5. Therefore
$[1,a,0,c]$ is #P-hard when $c\neq 0,\pm 1$. ∎

###  4.4 Dichotomy for $[1,a,b,c]$ when $abc\neq 0$

We need three lemmas to handle some special cases. Lemma 4.19 is a part of
Theorem 4.16 (one verifies that $G_{1}$ works, in fact for
$[1,-b^{2},b,-b^{3}]$ the condition (4.2) amounts to $b=1$, and the $b=0$ case
is degenerate thus trivially in FP). For convenience, we state it explicitly
here.

######  Lemma 4.19.

The problem $[1,-b^{2},b,-b^{3}]$ with $b\in\mathbb{Q}$ is #P-hard unless
$b=0,\pm 1$, which is in FP.

The next lemma is not part of Theorem 4.16 since the condition (4.2) fails for
$[1,a,-\frac{1}{a},-1]$.

######  Lemma 4.20.

The problem $[1,a,-\frac{1}{a},-1]$ with $a\in\mathbb{Q}$, $a\neq 0$ is
#P-hard unless $a=\pm 1$, in which case it is in FP.

###### Proof.

If $a=\pm 1$, $[1,1,-1-1]$ is affine and $[1,-1,1,-1]$ is degenerate, both of
which are in FP. Now we assume $a\neq\pm 1$ (so the matrix
$\left[\begin{smallmatrix}a^{-2}&a\\\ 1&1\end{smallmatrix}\right]$ is
invertible). We use the ternary gadget $G_{3}$ to get the signature
$g=[3a^{3}+\frac{1}{a^{3}}+4,a^{4}-\frac{1}{a^{2}},-a^{2}+\frac{1}{a^{4}},a^{3}+\frac{3}{a^{3}}+4]$
on LHS. A direct computation (using Mathematica) shows that $G_{1}$ always
works for $g$ unless $a=-1$. Therefore, by Theorem 4.16 we have $g$ is #P-hard
and then $[1,a,-\frac{1}{a},-1]$ is #P-hard unless $g$ is in the tractable
cases in Theorem 2.1. The only solution for $g$ being in the tractable cases
in Theorem 2.1 is $a=\pm 1$. This completes our proof. ∎

######  Lemma 4.21.

The problem $[1,a,b,ab]$ with $a,b\in\mathbb{Q}$ and $a,b\neq 0$ is #P-hard
unless it is degenerate or affine, which is in FP.

###### Proof.

(a)

(b)

Figure 25: Two gadgets where each triangle represents the unary gadget $[1,a]$

If $a=-1$ and $b=\pm 1$ then problem is in FP. Indeed, $[1,-1,1,-1]$ is
degenerate, and $[1,-1,-1,1]$ can be transformed to matchgate; both problems
are in FP. We therefore now assume it is not the case that both $a=-1$ and
$b=\pm 1$.

We first use $G_{3}$ to construct a ternary signature
$h=[-b^{4}+3b^{2}-2,b^{4}-2b^{3}-b^{2}+2b,2b^{3}-b^{2}-2b+1,-2b^{4}+3b^{2}-1]$
on LHS, which can be normalized to $h=[2-b^{2},b^{2}-2b,2b-1,1-2b^{2}]$ after
dividing $(b+1)(b-1)$. Using gadget $G_{1}$, we have a degenerate matrix
$G_{1}=\left[\begin{smallmatrix}1&b\\\
a&ab\end{smallmatrix}\right]=\left[\begin{smallmatrix}1\\\
a\end{smallmatrix}\right]\cdot\left[\begin{smallmatrix}1&b\end{smallmatrix}\right]$.
We get $[1,b]$ on RHS if $[1,a]$ can appropriately form some nonzero global
factor.

Figure 25 indicates two different ways of “absorbing” $[1,a]$ on LHS.
Importantly, we place $g$ instead of $[1,a,b,ab]$ on the square vertex. Figure
25(a) provides a factor $1+a^{3}$ which is nonzero if $a\neq-1$. When $a=-1$,
Figure 25(b) provides a factor $2b^{2}-4b+2=2(b-1)^{2}$ which is nonzero
unless $b=1$. Therefore, we can interpolate $[1,b]$ on RHS. Connect $[1,b]$
back to $[1,a,b,ab]$ on LHS and we get the binary signature
$g=[1+ab,a+b^{2},b+ab^{2}]$. If $a+b^{2}=0$, the given signature is
$[1,-b^{2},b,-b^{3}]$ which, according to Lemma 4.19, is #P-hard (the
exceptions in Lemma 4.19 do not apply as $b\neq 0$ and if $b=\pm 1$ then
$a=-b^{2}=-1$ which is excluded.) Now we assume $a+b^{2}\neq 0$. Normalize $g$
by dividing $a+b^{2}$, we have the binary signature
$[\frac{1+ab}{a+b^{2}},1,\frac{b+ab^{2})}{a+b^{2}}]$ on LHS. Applying
Corollary 4.5 to $g$, it is #P-hard (and so is the given signature
$[1,a,b,ab]$) unless

  1. 1.

$(1+ab)(b+ab^{2})=(a+b^{2})^{2}$. This implies
$\left(a^{2}-b\right)\left(b^{3}-1\right)=0$. If $a^{2}-b=0$, the given
signature is $[1,a,a^{2},a^{3}]$ and is degenerate. If $b^{3}-1=0$, since
$b\in\mathbb{Q}$, we have $b=1$ and $a\neq-b^{2}=-1$, and the given signature
is $[1,a,1,a]$. This is resolved by Lemma 4.2.

  2. 2.

$\frac{1+ab}{a+b^{2}}=1$ and $\frac{b+ab^{2}}{a+b^{2}}=-1$. Dividing the two
expressions gives $b=-1$. This implies $a=0$ and therefore violates our
assumption that $a\neq 0$.

  3. 3.

$\frac{1+ab}{a+b^{2}}=-1$ and $\frac{b+ab^{2}}{a+b^{2}}=1$. No $(a,b)$ pair
solves these two equations, under the assumption $a+b^{2}\neq 0$.

  4. 4.

$\frac{1+ab}{a+b^{2}}=\frac{b+ab^{2}}{a+b^{2}}$. We have either $b=1$ or
$ab=-1$. If $b=1$, then $[1,a,b,ab]$ becomes $[1,a,1,a]$ which is #P-hard by
Lemma 4.2 unless $a=0$ (this violates our assumption) or $a=\pm 1$, in which
cases the signature is affine and therefore the problem is in FP. If $ab=-1$,
then $[1,a,b,ab]$ becomes $[1,a,-\frac{1}{a},-1]$ which is #P-hard by Lemma
4.20 unless $a=\pm 1$, in which cases the signature is affine and therefore
the problem is in FP.

Note that since $a,b\neq 0$, $[1,a,b,ab]$ cannot be Gen-Eq. The lemma is
proved. ∎

Now we prove

######  Theorem 4.22.

The problem $[1,a,b,c]$ with $a,b,c\in\mathbb{Q}$, $abc\neq 0$, is #P-hard
unless it is in the tractable cases in Theorem 2.1.

###### Proof.

By Proposition 4.8, Theorem 4.16 and Lemma 4.21 it suffices to consider the
case when the ratio of two eigenvalues in
$G_{1}=\left[\begin{smallmatrix}1&b\\\ a&c\end{smallmatrix}\right]$ is a root
of unity and $c\neq ab$. If the ratio of eigenvalues of $G_{1}$ is a root of
unity, we know at least one condition in (4.2) holds. For convenience, we list
the conditions in (4.2) here and label them as $R_{i}$ where $i=1,2,3,4,5$:

$R=\bigvee_{i=1}^{5}R_{i},\ \ \text{where}\begin{cases}R_{1}:c=-1\\\
R_{2}:ab+c^{2}+c+1=0\\\ R_{3}:2ab+c^{2}+1=0\\\ R_{4}:3ab+c^{2}-c+1=0\\\
R_{5}:4ab+c^{2}-2c+1=0\\\ \end{cases}$ (4.6)

We apply $G_{3}$ on $[1,a,b,c]$, i.e. placing squares to be $[1,a,b,c]$ and
circles to be $=_{3}$, to produce a ternary signature
$[w,x,y,z]=[1+3a^{3}+3a^{2}b^{2}+b^{3}c,a+a^{4}+2a^{2}b+a^{2}bc+2ab^{3}+b^{2}c^{2},a^{2}+ab^{2}+2a^{3}b+b^{4}+2ab^{2}c+bc^{3},a^{3}+3a^{2}b^{2}+3b^{3}c+c^{4}]$.
If $w\neq 0$ and $G_{1}$ works on $[w,x,y,z]$, by Theorem 4.16 we have
$[w,x,y,z]$ is #P-hard and thus $[1,a,b,c]$ is #P-hard unless at least one
condition $S_{i}$ listed below holds, where $i=1,2,3,4,5,6,7$:

$S=\bigvee_{i=1}^{7}S_{i}\ \ \text{where}\begin{cases}S_{1}:x^{2}=wy\wedge
y^{2}=xz\ (\text{degenerate form})\\\ S_{2}:x=0\wedge y=0\ (\text{Gen-Eq
form})\\\ S_{3}:w=y\wedge x=0\wedge z=0\ (\text{affine form $[1,0,1,0]$})\\\
S_{4}:w+y=0\wedge x=0\wedge z=0\ (\text{affine form $[1,0,-1,0]$})\\\
S_{5}:w=z\wedge x=y\ (\text{matchgate-realizable form
$[a^{\prime},b^{\prime},b^{\prime},a^{\prime}]$})\\\ S_{6}:w=-z\wedge x=-y\
(\text{matchgate-realizable form
$[a^{\prime},b^{\prime},-b^{\prime},-a^{\prime}]$})\\\ S_{7}:-w-2x=y\wedge
2w+3x=z\ (\text{form
$[3a^{\prime}+b^{\prime},-a^{\prime}-b^{\prime},-a^{\prime}+b^{\prime},3a^{\prime}-b^{\prime}]$})\end{cases}$
(4.7)

Note that the affine forms $[1,1,-1,-1]$ and $[1,-1,-1,1]$ are special forms
of $[a,b,b,a]$ and $[a,b,-b,-a]$. Solve the equation system $R\wedge S$ for
variables $a,b,c\in\mathbb{Q}$, we have the following solutions:

  * •

$a=c=-1,b=1$; the problem $[1,-1,1,-1]$ is in FP since it is degenerate;

  * •

$a=1,b=c=-1$; the problem $[1,1,-1,-1]$ is in FP since it is affine;

  * •

$a=c=1,b=-1$; the problem $[1,1,-1,1]$ is #P-hard (use the gadget $G_{3}$ to
produce $[1,1,-1,3]$ after flipping 0’s and 1’s, then use it again to produce
$[1,1,-5,19]$ which is #P-hard by Theorem 4.16. Note that we need to apply
$G_{3}$ twice in order that the condition that $G_{1}$ works in Theorem 4.16
is satisfied for the newly created ternary signature);

  * •

$a=-b,c=-1$; the problem $[1,a,-a,-1]$ is matchgate-transformable and thus in
FP.

Continuing the discussion for the ternary signature $[w,x,y,z]$, it remains to
consider the case when $w=0$ or $G_{1}$ does not work on $[w,x,y,z]$. For
$w\neq 0$ we normalize $[w,x,y,z]$ to be
$[1,\frac{x}{w},\frac{y}{w},\frac{z}{w}]$ and substituting
$\frac{x}{w},\frac{y}{w},\frac{z}{w}$ into $a,b,c$ respectively in (4.2), we
get at least one condition $T_{i}$ listed below, where $i=1,2,3,4,5,6$:

$T=\bigvee_{i=1}^{6}T_{i},\ \ \text{where}\begin{cases}T_{1}:zw+w^{2}=0\\\
T_{2}:xy+z^{2}+zw+w^{2}=0\\\ T_{3}:2xy+z^{2}+w^{2}=0\\\
T_{4}:3xy+z^{2}-zw+w^{2}=0\\\ T_{5}:4xy+z^{2}-2zw+w^{2}=0\\\ T_{6}:xy=wz\\\
\end{cases}$ (4.8)

Note that $T_{1}$ incorporates the case when $w=0$. So we have the condition
$R\wedge T$. We now apply $G_{3}$ once again using $[w,x,y,z]$ to produce
another new ternary signature $[w_{2},x_{2},y_{2},z_{2}]$ where
$w_{2}=w^{4}+3wx^{3}+3x^{2}y^{2}+y^{3}z$,
$x_{2}=w^{3}x+2wx^{2}y+x^{4}+2xy^{3}+x^{2}yz+y^{2}z^{2}$,
$y_{2}=w^{2}x^{2}+wxy^{2}+2x^{3}y+y^{4}+2xy^{2}z+yz^{3}$,
$z_{2}=wx^{3}+3x^{2}y^{2}+3y^{3}z+z^{4}$. Similarly as the previous argument,
if $w_{2}\neq 0$ and $G_{1}$ works on $[w_{2},x_{2},y_{2},z_{2}]$, we know
$[w_{2},x_{2},y_{2},z_{2}]$ is #P-hard and thus $[1,a,b,c]$ is #P-hard unless
at least one condition $U_{i}$ listed below holds, where $i=1,2,3,4,5,6,7$:

$U=\bigvee_{i=1}^{7}U_{i},\ \
\text{where}\begin{cases}U_{1}:x_{2}^{2}=w_{2}y_{2}\wedge
y_{2}^{2}=x_{2}z_{2}\ (\text{degenerate form})\\\ U_{2}:x_{2}=0\wedge y_{2}=0\
(\text{Gen-Eq form})\\\ U_{3}:w_{2}=y_{2}\wedge x_{2}=0\wedge z_{2}=0\
(\text{affine form $[1,0,1,0]$})\\\ U_{4}:w_{2}+y_{2}=0\wedge x_{2}=0\wedge
z_{2}=0\ (\text{affine form $[1,0,-1,0]$})\\\ S_{5}:w_{2}=z_{2}\wedge
x_{2}=y_{2}\ (\text{matchgate-realizable form
$[a^{\prime},b^{\prime},b^{\prime},a^{\prime}]$})\\\ S_{6}:w_{2}=-z_{2}\wedge
x_{2}=-y_{2}\ (\text{matchgate-realizable form
$[a^{\prime},b^{\prime},-b^{\prime},-a^{\prime}]$})\\\
S_{7}:-w_{2}-2x_{2}=y_{2}\wedge 2w_{2}+3x_{2}=z_{2}\ (\text{form
$[3a^{\prime}+b^{\prime},-a^{\prime}-b^{\prime},-a^{\prime}+b^{\prime},3a^{\prime}-b^{\prime}]$})\end{cases}$
(4.9)

Solve the equation system $R\wedge T\wedge U$ for rational-valued variables
$a,b,c$, we have the following solutions:

  * •

$a=c=-1,b=1$; the problem $[1,-1,1,-1]$ is in FP since it is degenerate;

  * •

$a=1,b=c=-1$; the problem $[1,1,-1,-1]$ is in FP since it is affine;

  * •

$a=-1,b=c=1$; the problem $[1,-1,1,1]$ is #P-hard (use the gadget $G_{4}$ to
produce $[1,1,-1,3]$, use it again to produce $[1,1,-5,19]$ which is #P-hard
by Theorem 4.16);

  * •

$a=c=1,b=-1$; the problem $[1,1,-1,1]$ is #P-hard (this is the reversal of
$[1,-1,1,1]$);

Otherwise, we know $w_{2}=0$ or $G_{1}$ does not work on
$[w_{2},x_{2},y_{2},z_{2}]$. Similarly, we know at least one condition $V_{i}$
listed below holds, where $i=1,2,3,4,5,6$:

$V=\bigvee_{i=1}^{6}V_{i},\ \
\text{where}\begin{cases}V_{1}:z_{2}w_{2}+w_{2}^{2}=0\\\
V_{2}:x_{2}y_{2}+z_{2}^{2}+z_{2}w_{2}+w_{2}^{2}=0\\\
V_{3}:2x_{2}y_{2}+z_{2}^{2}+w_{2}^{2}=0\\\
V_{4}:3x_{2}y_{2}+z_{2}^{2}-z_{2}w_{2}+w_{2}^{2}=0\\\
V_{5}:4x_{2}y_{2}+z_{2}^{2}-2z_{2}w_{2}+w_{2}^{2}=0\\\
V_{6}:x_{2}y_{2}=w_{2}z_{2}\\\ \end{cases}$ (4.10)

Finally, solve the equation system $R\wedge T\wedge V$ for variables
$a,b,c\in\mathbb{Q}$, we have the following solutions:

  * •

$a=-1,b=c=1$; the problem $[1,-1,1,1]$ is #P-hard (see the case above for
$R\wedge T\wedge U$);

  * •

$a=c=1,b=-1$; the problem $[1,1,-1,1]$ is #P-hard (this is the reversal of
$[1,-1,1,1]$);

  * •

$a=-b,c=-1$; the problem $[1,a,-a,-1]$ is matchgate-transformable and thus in
FP.

The proof of Theorem 4.22 is now complete. ∎

##  5 Dichotomy for $[0,a,b,0]$

We now finish the discussion for $[0,a,b,0]$ with the help of previous
theorems on $[1,a,b,c]$.

######  Theorem 5.1.

The problem $[0,a,b,0]$ with $a,b\in\mathbb{Q},ab\neq 0$ is #P-hard unless
$a=\pm b$.

###### Proof.

We apply the gadget $G_{3}$ on $[0,a,b,0]$ to produce the ternary signature
$g=[3a^{2}b^{2},a(a^{3}+2b^{3}),b(2a^{3}+b^{3}),3a^{2}b^{2}]$.

We can normalize $g$ to be the form $[1,a^{\prime},b^{\prime},c^{\prime}]$.
Since $a,b,c\in\mathbb{Q}$, we have $a^{\prime}b^{\prime}c^{\prime}\neq 0$. By
Theorem 4.22, we know $[1,a^{\prime},b^{\prime},c^{\prime}]$ is #P-hard (and
so is $[0,a,b,0]$) unless it is in the tractable cases in Theorem 2.1.
However, the problem $[1,a^{\prime},b^{\prime},c^{\prime}]$ in FP implies
$a=\pm b$. This finishes the proof. ∎

If now $a=b=0$, then the Holant value is 0 and the problem is trivially in
$\operatorname{FP}$. Suppose exactly one of $a$ and $b$ is 0. In this case, by
normalizing and possibly flipping 0 and 1 in the input, it suffices to
consider the ternary signature $[0,1,0,0]$.

Figure 26: The cross-over-pinned-0 gadget $\mathcal{P}$

######  Theorem 5.2.

The problem $\operatorname{Pl-Holant}\left([0,1,0,0]\mid(=_{3})\right)$ is
#P-complete.

###### Proof.

In [DF86], Dyer and Frieze proved the problem Planar-X3C NP-complete: An input
is a collection $\cal S$ of 3-element subsets of a set $U$, where the
bipartite incidence graph is planar, and we ask for an exact cover of $U$ by
some ${\cal S^{\prime}}\subseteq{\cal S}$. Their reduction in fact produces
instances where every $x\in U$ appears in exactly two or three sets of $\cal
S$. One can further verify that their reduction is parsimonious. Thus, their
proof yields the #P-completeness for $\operatorname{Pl-
Holant}\left([0,1,0,0],[0,1,0]\mid(=_{3})\right)$. We prove our theorem by a
reduction

$\operatorname{Pl-
Holant}\left([0,1,0,0],[0,1,0]\mid(=_{3})\right)\leq_{T}\operatorname{Pl-
Holant}\left([0,1,0,0]\mid(=_{3})\right).$ (5.11)

Note that a unary pin-0 signature $\Delta_{0}$ connected to $[0,1,0,0]$
produces $[0,1,0]$. If we replace each $[0,1,0]$ in $\Omega$ by $[0,1,0,0]$
connected with $\Delta_{0}$, the Holant value is unchanged. So if we can
produce $\Delta_{0}$ on the RHS in $\operatorname{Pl-
Holant}\left([0,1,0,0]\mid(=_{3})\right)$, then (5.11) follows. But, in any
bipartite 3-regular problem _provably_ no construction can produce individual
unary signatures. Next, note that in any signature grid $\Omega$ of
$\operatorname{Pl-Holant}\left([0,1,0,0],[0,1,0]\mid(=_{3})\right)$, the
number of appearances of $[0,1,0]$ is congruent to $0\bmod 3$, by counting the
total degrees of LHS and RHS. Then, our idea is to create triples of
$\Delta_{0}$ so that we can apply them, one triple at a time.

There remains the difficulty of how to construct triples of $\Delta_{0}$ on
the RHS in the setting $\operatorname{Pl-
Holant}\left([0,1,0,0]\mid(=_{3})\right)$, and more importantly, not only the
construction must be planar but also we must be able to apply them in
$\Omega$, three at a time, in a planar fashion. Notice that the appearances of
$[0,1,0]$ in $\Omega$ generally do not allow this planar grouping (and indeed
the output instances in [DF86] do not have this property).

The following construction accomplishes all these requirements in one fell
swoop! The planar cross-over-pinned-0 gadget $\mathcal{P}$ is illustrated in
Figure 26, where we place $[0,1,0,0]$ at the squares and $=_{3}$ at the
circles. It has the following properties:

  1. 1.

externally the two left dangling edges are to be connected to LHS, and two
right dangling edges are to be connected to RHS;

  2. 2.

the two blue dangling edges are pinned to be 0;

  3. 3.

the two red dangling edges can be assigned to either 0 or 1, but must be the
same value, and either choice induces a unique assignment for the internal
edges.

Note also that if we “flip” $\mathcal{P}$ along the “axis” of the two blue
edges, thereby exchange the two red edges, we have a reflected copy of
$\mathcal{P}$, call it $\mathcal{P}^{\prime}$, where the North-East red edge
connects externally to LHS, and the South-West red edge connects externally to
RHS, exactly the opposite of $\mathcal{P}$.

Thus, the gadget $\mathcal{P}$ allows “passing over” one crossing edge (the
pair of red edges will take its place) while the two end blue edges are pinned
to 0. We can link any $k\geq 1$ copies of $\mathcal{P}$ or
$\mathcal{P}^{\prime}$ by the blue edges to “pass over” $k$ crossings. Note
that the linking of the two end blue edges respects the bipartite structure,
and $\mathcal{P}$ or $\mathcal{P}^{\prime}$ allow any individual bipartite
orientation of the crossed edge. We call this a linked $\mathcal{P}$ gadget.

Let $n=3m$ be the number of $[0,1,0]$ in $\Omega$ for some integer $m\geq 0$.
We now add $m$ new vertices on RHS assigned the signature $=_{3}$. We then use
three copies of the linked $\mathcal{P}$ gadgets to connect this $=_{3}$ to
three occurrences of $[0,1,0]$ in $\Omega$, while replacing the signatures
there by $[0,1,0,0]$. (If some passage from $=_{3}$ to $[0,1,0]$ does not
encounter any crossing edge, we will artificially introduce two such
crossings!) This defines a signature grid $\Omega^{\prime}$ in
$\operatorname{Pl-Holant}\left([0,1,0,0]\mid(=_{3})\right)$ with
$\operatorname{Holant}(\Omega^{\prime})=\operatorname{Holant}(\Omega)$. ∎

######  Remark 4.

One can easily construct a degenerate ternary signature
$[1,0,0,0]=[1,0]\otimes[1,0]\otimes[1,0]$ on RHS by placing circles to be
$[0,1,0,0]$ and squares to be $(=_{3})$ on $G_{2}$. However, we cannot apply
Theorem 3.2 and conclude that $\operatorname{Pl-
Holant}\left([0,1,0,0],[0,1,0]\mid(=_{3})\right)\leq_{T}\operatorname{Pl-
Holant}\left([0,1,0,0]\mid(=_{3})\right).$ See also Remark 1. The use of the
gadget $\mathcal{P}$ is essential.

##  6 Main Theorem

We are now ready to prove our main theorem. At the end of the proof there is a
flowchart of the logical structure for this proof of Theorem 2.1.

###### Proof of Theorem 2.1.

First, if $f_{0}=f_{3}=0$, we separate the discussion into whether
$f_{1}f_{2}\neq 0$. If $f_{1}f_{2}\neq 0$, by Theorem 5.1 we know that it is
#P-hard unless $f_{1}=f_{2}$, in which case it is matchgate-transformable and
thus in FP. If $f_{1}f_{2}=0$, then by Theorem 5.2 we know that it is #P-hard
unless $f_{1}=f_{2}=0$, in which case the problem is trivially in FP. This
finishes the case when $f_{0}=f_{3}=0$.

Assume now at least one of $f_{0}$ and $f_{3}$ is not $0$. By considering the
reversal of the signature, we can assume $f_{0}\neq 0$, then the signature
becomes $[1,a,b,c]$ after normalization.

If $c=0$, the dichotomy for $[1,a,b,0]$ is proved in Theorem 4.17.

If in $[1,a,b,c]$, $c\neq 0$, then $a$ and $b$ are symmetric by flipping. Now
if $ab=0$, we can assume $b=0$ by the afore-mentioned symmetry, i.e., the
signature becomes $[1,a,0,c]$. By Theorem 4.18, it is #P-hard unless $a=0$, in
which case it is Gen-Eq.

Finally, for the problem $[1,a,b,c]$ where $abc\neq 0$, Theorem 4.22 proves
the dichotomy that it is #P-hard unless the signature is in the tractable
cases of Theorem 2.1. ∎

Flowchart of proof structure:

$[f_{0},f_{1},f_{2},f_{3}]$ Dichotomy for $[0,a,b,0]$, Theorem 5.1 $[1,a,b,c]$
Dichotomy for $[1,a,b,0]$, Theorem 4.17 Dichotomy for $[1,a,0,c]$, Theorem
4.18 Dichotomy in Theorem 4.22 Hardness for $[0,1,0,0]$, Theorem 5.2 if
$f_{0}=f_{3}=0$ and $f_{1}f_{2}\neq 0$ else, possibly by flipping if $c=0$ if
$c\neq 0$ and $ab=0$ else (i.e., $abc\neq 0$) if $f_{0}=f_{3}=0$ and
$f_{1}f_{2}=0$

## References

  * [ABHM00] Robert E. L. Aldred, Sheng Bau, Derek A. Holton, and Brendan D. McKay.  Nonhamiltonian 3-connected cubic planar graphs.  SIAM J. Discret. Math., 13(1):25–32, 2000.
  * [Bac21] Miriam Backens.  A full dichotomy for Holantc, inspired by quantum computation.  SIAM J. Comput., 50(6):1739–1799, 2021.
  * [CC17] Jin-Yi Cai and Xi Chen.  Complexity Dichotomies for Counting Problems: Volume 1, Boolean Domain.  Cambridge University Press, 2017.
  * [CF17] Jin-Yi Cai and Zhiguo Fu.  Holographic algorithm with matchgates is universal for planar #CSP over Boolean domain.  In STOC, pages 842–855. ACM, 2017.
  * [CFGW22] Jin-Yi Cai, Zhiguo Fu, Heng Guo, and Tyson Williams.  FKT is not universal - A planar Holant dichotomy for symmetric constraints.  FOCS 2015: 1259-1276. Theory Comput. Syst., 66(1):143–308, 2022\.
  * [CFL23] Jin-Yi Cai, Austen Z. Fan, and Yin Liu.  Bipartite 3-regular counting problems with mixed signs.  Journal of Computer and System Sciences, 135:15–31, 2023.
  * [CG19] Jin-Yi Cai and Artem Govorov.  Perfect matchings, rank of connection tensors and graph homomorphisms.  In SODA, pages 476–495. SIAM, 2019.
  * [CL11] Jin-Yi Cai and Pinyan Lu.  Holographic algorithms: From art to science.  J. Comput. Syst. Sci., 77(1):41–61, 2011.
  * [CLX17] Jin-Yi Cai, Pinyan Lu, and Mingji Xia.  Holographic algorithms with matchgates capture precisely tractable planar #CSP.  SIAM J. Comput., 46(3):853–889, 2017.
  * [DF86] Martin E. Dyer and Alan M. Frieze.  Planar 3DM is NP-complete.  J. Algorithms, 7(2):174–184, 1986.
  * [FLS07] Michael Freedman, László Lovász, and Alexander Schrijver.  Reflection positivity, rank connectivity, and homomorphism of graphs.  J. Amer. Math. Soc., 20(1):37–51, 2007.
  * [GW20] Heng Guo and Tyson Williams.  The complexity of planar Boolean #CSP with complex weights.  J. Comput. Syst. Sci., 107:1–27, 2020.
  * [HM88] Derek A. Holton and Brendan D. McKay.  The smallest non-hamiltonian 3-connected cubic planar graphs have 38 vertices.  J. Comb. Theory, Ser. B, 45(3):305–319, 1988.
  * [HT06] Christopher Carl Heckman and Robin Thomas.  Independent sets in triangle-free cubic planar graphs.  J. Comb. Theory, Ser. B, 96(2):253–275, 2006.
  * [Jer87] Mark R. Jerrum.  Two-dimensional monomer-dimer systems are computationally intractable.  J. Statist. Phys., 48(1):121–134, 1987.
  * [Kas61] Pieter W. Kasteleyn.  The statistics of dimers on a lattice: I. the number of dimer arrangements on a quadratic lattice.  Physica, 27(12):1209–1225, 1961.
  * [Kas67] Pieter W. Kasteleyn.  Graph theory and crystal physics.  Graph theory and theoretical physics, pages 43–110, 1967.
  * [KC16] Michael Kowalczyk and Jin-Yi Cai.  Holant problems for 3-regular graphs with complex edge functions.  Theory Comput. Syst., 59(1):133–158, 2016.
  * [Lar93] Philippe Laroche.  Planar 1-in-3 satisfiability is NP-complete.  Comptes Rendus de L Academie des Sciences Serie I-Mathematique, 316(4):389–392, 1993.
  * [Lic82] David Lichtenstein.  Planar formulae and their uses.  SIAM J. Comput., 11(2):329–343, 1982.
  * [MR01] Cristopher Moore and John M. Robson.  Hard tiling problems with simple tiles.  Discret. Comput. Geom., 26(4):573–590, 2001.
  * [NRR20] Marc Noy, Clément Requilé, and Juanjo Rué.  Further results on random cubic planar graphs.  Random Struct. Algorithms, 56(3):892–924, 2020.
  * [Sch74] David E. Scheim.  The number of edge 3-colorings of a planar cubic graph as a permanent.  Discret. Math., 8(4):377–382, 1974.
  * [Sch78] Thomas J. Schaefer.  The complexity of satisfiability problems.  In STOC, pages 216–226. ACM, 1978.
  * [TF61] Harold N. V. Temperley and Michael E. Fisher.  Dimer problem in statistical mechanics-an exact result.  Philosophical Magazine, 6(68):1061–1063, 1961.
  * [Vad01] Salil P. Vadhan.  The complexity of counting in sparse, regular, and planar graphs.  SIAM Journal on Computing, 31(2):398–427, 2001.
  * [Val79] Leslie G. Valiant.  The complexity of computing the permanent.  Theor. Comput. Sci., 8:189–201, 1979.
  * [Val08] Leslie G. Valiant.  Holographic algorithms.  SIAM J. Comput., 37(5):1565–1594, 2008.

$x_{0}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$y_{0}$$y_{1}$$y_{2}$$y_{3}$$y_{4}$$x^{\prime}_{0}$$x^{\prime}_{1}$$x^{\prime}_{2}$$x^{\prime}_{3}$$x^{\prime}_{4}$$y^{\prime}_{3}$$y^{\prime}_{4}$
(a) $(x^{\prime}_{0},x^{\prime}_{3},x^{\prime}_{4})=(0,0,0)$

$x_{0}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$y_{0}$$y_{1}$$y_{2}$$y_{3}$$y_{4}$$x^{\prime}_{0}$$x^{\prime}_{1}$$x^{\prime}_{2}$$x^{\prime}_{3}$$x^{\prime}_{4}$$y^{\prime}_{3}$$y^{\prime}_{4}$
(b) $(x^{\prime}_{0},x^{\prime}_{3},x^{\prime}_{4})=(0,1,0)$

$x_{0}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$y_{0}$$y_{1}$$y_{2}$$y_{3}$$y_{4}$$x^{\prime}_{0}$$x^{\prime}_{1}$$x^{\prime}_{2}$$x^{\prime}_{3}$$x^{\prime}_{4}$$y^{\prime}_{3}$$y^{\prime}_{4}$
(c) $(x^{\prime}_{0},x^{\prime}_{3},x^{\prime}_{4})=(1,0,0)$

$x_{0}$$x_{1}$$x_{2}$$x_{3}$$x_{4}$$y_{0}$$y_{1}$$y_{2}$$y_{3}$$y_{4}$$x^{\prime}_{0}$$x^{\prime}_{1}$$x^{\prime}_{2}$$x^{\prime}_{3}$$x^{\prime}_{4}$$y^{\prime}_{3}$$y^{\prime}_{4}$
(d) $(x^{\prime}_{0},x^{\prime}_{3},x^{\prime}_{4})=(1,1,0)$

Figure 27: Geometric picture in the proof of Theorem 3.2