Department of Computer Science, Rice University, USA Department of Computer
Science, Rice University<EMAIL_ADDRESS>Moshe Y. Vardi and Zhiwei Zhang
<ccs2012> <concept> <concept_id>10003752.10003809.10003635</concept_id>
<concept_desc>Theory of computation Graph algorithms analysis</concept_desc>
<concept_significance>300</concept_significance> </concept> </ccs2012>
[300]Theory of computation Graph algorithms analysis Work supported in part by
NSF grants IIS-1527668, CCF-1704883, IIS-1830549, DoD MURI grant
N00014-20-1-2787, Andrew Ladd Graduate Fellowship of Rice Ken Kennedy
Institute, and an award from the Maryland Procurement Office.2 Arxiv Arxiv 42

# Quantum-Inspired Perfect Matching under Vertex-Color Constraints

Moshe Y. Vardi  Zhiwei Zhang 111The author list has been sorted alphabetically
by last name; this should not be used to determine the extent of authors’
contributions. Corresponding author: Zhiwei Zhang (zhiwei@rice.edu).

###### Abstract

We propose and study the graph-theoretical problem PM-VC: _perfect matching
under vertex-color constraints on graphs with bi-colored edges_. PM-VC is of
special interest because of its motivation from quantum-state identification
and quantum-experiment design, as well as its rich expressiveness, i.e., PM-VC
subsumes many constrained matching problems naturally, such as exact perfect
matching. We give complexity and algorithmic results for PM-VC under two types
of vertex color constraints: 1) symmetric constraints (PM-VC-Sym) and 2)
decision-diagram constraints (PM-VC-DD).

We prove that PM-VC-Sym is in RNC via a symbolic determinant algorithm, which
can be derandomized on planar graphs. Moreover, PM-VC-Sym can be expressed in
extended MSO, which encourages our design of an efficient dynamic programming
algorithm for PM-VC-Sym on bounded-treewidth graphs. For PM-VC-DD, we reveal
its NP-hardness by a graph-gadget technique. Our novel results for PM-VC
provide insights to both constrained matching and scalable quantum experiment
design.

###### keywords:

Quantum Computing, Perfect Matching, Symbolic Determinant, Dynamic
Programming, Graph Gadget

###### category:

##  1 Introduction

Quantum computing is widely believed to be one of the most promising research
areas that could be a game changer, as it studies a radical new type of
computational model [16]. Using quantum computing, it is hoped to tackle
classically hard problems that are believed to be intractable for traditional
computers, such as factorization by Shor’s Algorithm [36, 37]. Nevertheless,
implementations of quantum computers today have not yet reached the
satisfactory scalability and reliability to solve practical problems. On the
path of designing useful quantum computers, quantum experiments [33] are
necessary, whose design involves solving classical problems. Hence, a reverse
research direction regarding leveraging classical algorithms to help design
quantum experiments has emerged [23, 17].

Recently, a surprising connection has been discovered between quantum state of
a quantum optical circuit and perfect matching (PM) under vertex-color
constraints on graphs with bi-colored edges [28]. For example, whether the
quantum state of an optical circuit as a superposition exhibits GHZ state is
equivalent to whether a graph contains a mono-chromatic perfect matching [20].
Solving the constrained PM problem provides important understanding to
properties of quantum circuits.

Deciding whether perfect matchings exist in a graph is well-known to be in
PTIME via Blossom Algorithm [18]. In practice, additional restrictions on
perfect matchings are often needed, which make the perfect-matching problem
display interesting complexity and algorithmic properties [19]. While existing
work studied PMs under edge color or weight constraints, insufficient effort
has been put to PM under vertex-color constraints on graphs with bi-colored
edges, motivated by applications in quantum computing.

We propose and investigate the quantum-inspired graph-theoretical problem of
whether a graph with bi-colored edges has a Perfect Matching under Vertex-
Color constraints (PM-VC). We point out that the complexity of PM-VC depends
on the specific representation of the vertex-color constraints. We study two
constraint structures, yielding two important instances of PM-VC: 1) PMs under
symmetric constraints (PM-VC-Sym) and 2) PMs constrained by decision diagrams
(PM-VC-DD). We show that PM-VC-Sym is in RNC via symbolic-determinant
approaches, which can be derandomized on planar graphs by Pfaffian
orientation. Moreover, PM-VC-Sym is expressible in extended monadic second-
order logic (MSO), which encourages us to design a dynamic programming
algorithm for bounded-treewidth graphs. For the more expressive problem PM-VC-
DD, we prove its NP-hardness by reducing 3-SAT to it through a novel gadget
technique. Our results not only fill the knowledge gap about restricted
perfect matching under vertex-related constraints and bi-colored graphs, but
also shed light on the hardness of identifying properties of large-scale
quantum circuits.

The main theoretical contributions of this paper are: PM-VC-Sym is in RNC2 on
general graphs and NC2 on planar graphs, with bounded number of colors (Sec.
5.1). PM-VC-Sym is expressible in extended MSO and is in PTIME on bounded-
treewidth graphs with bounded number of colors (Sec. 5.2). PM-VC-DD with at
least two colors is NP-hard (Sec. 6).

###  1.1 Paper Organization

Section 2 presents preliminaries. Section 3 describes the motivation of PM-VC
from quantum computing. Section 4 summarizes related work. In Section 5 we
give positive complexity and algorithmic results for PM-VC-Sym. In Section 6
we prove the NP-hardness of PM-VC-DD. Section 7 concludes the paper and lists
open problems and future directions. Due to space limit, most proofs of the
results in this paper are deferred until the appendix.

##  2 Problem Definitions and Preliminaries

###  2.1 Complexity Classes

Let P be the complexity class of polynomially solvable problems. RP is the
class of problems where a polynomial randomized algorithm $\mathcal{R}$ exists
such that 1) if the actual answer is “yes”, then $\mathcal{R}$ returns “yes”
with constant non-zero probability; 2) if the answer is “no”, $\mathcal{R}$
always returns “no”. NC is the class of problems solvable by a parallel
algorithm in logarithmic time with polynomially many processors. NCi is the
subset of NC of problems solvable in $O(\log^{i}n)$ time by polynomially many
processors. RNC and RNCi are the randomized analogs of NC and NCi,
respectively. We have NC${}^{1}\subseteq$ NC${}^{2}\subseteq\cdots\subseteq$
NC$\subseteq P$ and RNC${}^{1}\subseteq$ RNC${}^{2}\subseteq\cdots\subseteq$
RNC$\subseteq$ RP. For two problems $\mathcal{P}_{1},\mathcal{P}_{2}$, we have
that $\mathcal{P}_{1}\leq_{P}\mathcal{P}_{2}$ if there is a polynomial
reduction from $\mathcal{P}_{1}$ to $\mathcal{P}_{2}$. We denote
$\mathcal{P}_{1}<_{P}\mathcal{P}_{2}$ if
$\mathcal{P}_{1}\leq_{P}\mathcal{P}_{2}$ and
$\mathcal{P}_{2}\not\leq_{P}\mathcal{P}_{1}$. Finally,
$\mathcal{P}_{1}=_{P}\mathcal{P}_{2}$ if
$\mathcal{P}_{1}\leq_{P}\mathcal{P}_{2}$ and
$\mathcal{P}_{2}\leq_{P}\mathcal{P}_{1}$.

###  2.2 Perfect Matchings in Graphs with Bi-colored Edges under Vertex-Color
Constraints

Figure 1: Left: a graph $G$ with bi-colored edges. Right: all perfect
matchings of $G$ and their inherited vertex colorings.

######  Definition 2.1.

(Graphs with bi-colored edges) In this paper, a “graph” refers to an
undirected, non-simple 222Self-loops are prohibited but multiple edges between
the same pair of vertices are allowed. graph with bi-colored edges. Formally,
a graph $G$ is a tuple $(V,E,d)$, where $V$ is the set of vertices with
$|V|=n$, $E$ is the set of bi-colored edges and $d$ is the number of colors.
For each edge $e\in E$ that connects $u$ and $v$, there are two colors
$c_{u}^{e},c_{v}^{e}\in\\{1,\cdots,d\\}$ that are associated with $u$ and $v$,
respectively, i.e., $e=\\{(u,c_{u}^{e}),(v,c_{v}^{e})\\}$. If
$c_{u}^{e}=c_{v}^{e}$, we call the edge $e$ monochromatic, otherwise $e$ is
bi-colored. See Figure 1 (left) as an example.

######  Definition 2.2.

(Vertex coloring) A vertex coloring of graph $G=(V,E,d)$ is a mapping $c$ from
vertices to color indices i.e., $c:V\to\\{1,\cdots,d\\}$. Alternatively one
can write $c\in{\\{1,\cdots,d\\}}^{V}$.

######  Definition 2.3.

(Perfect matchings and their inherited vertex colorings) [27] A perfect
matching $P$ of a graph $G$ is a subset of edges, i.e., $P\subseteq E$, such
that for each vertex $v\in V$, exactly one edge in $P$ is adjacent to $v$. For
a perfect matching $P$ of a graph $G$, its _inherited vertex coloring_ ,
denoted by $c^{P}:V\to\\{1,\cdots,d\\}$ is defined as follows: for each vertex
$v$, let $e$ be the unique edge that is adjacent to $v$, then
$c^{P}(v)=c_{v}^{e}$. See Figure 1 (right) for examples.

######  Definition 2.4.

(Legal perfect matchings w.r.t. vertex-color constraints) Suppose a system of
vertex-color constraints defines a set of “legal” vertex colorings
$\mathcal{C}\subseteq{\\{1,\cdots,d\\}}^{V}$. A perfect matching is _legal_
(w.r.t. $\mathcal{C}$) if its inherited vertex coloring is legal, i.e.,
$c^{P}\in\mathcal{C}$.

######  Problem 2.5.

(Perfect Matching with Vertex Coloring constraints, PM-VC) Given a graph
$G=(V,E,d)$ and a set $\mathcal{C}$ of legal vertex colorings defined by
vertex-color constraints, does $G$ have a legal perfect matching w.r.t.
$\mathcal{C}$?

In the case of only polynomially many legal vertex colorings, e.g., “all
vertices have the same color”, the problem is easy, as shown in the following
proposition. The idea is that for each vertex coloring $c$ in $\mathcal{C}$,
we can call Blossom Algorithm on a subgraph of $G$ with only edges whose
colors align with $c$.

######  Proposition 2.6.

If $|\mathcal{C}|$ is polynomially bounded by $|G|$, then PM-VC is in $P$.

The challenging part of PM-VC is when $|\mathcal{C}|$ is exponential, such
that it is infeasible to explicitly enumerate $\mathcal{C}$. In this case,
$\mathcal{C}$ needs to be defined implicitly by vertex-color constraints. We
study two representations of vertex-color constraints: symmetric constraints
and decision diagrams.

###  2.3 Symmetric Constraints and PM-VC-Sym

######  Definition 2.7.

(Symmetric constraints)  For a system of vertex-color constraints, let the
vertex coloring set it defines be $\mathcal{C}$. The system of vertex-color
constraints is _symmetric_ if whether a vertex coloring $c$ is in
$\mathcal{C}$ is determined by the count of each color $i\in\\{1,\cdots,d\\}$
in $c$, denoted by $\texttt{count}(c,i)=|\\{v|c(v)=i,v\in V\\}|$.

For example, “there is only one red vertex”
($\texttt{count}(c,\texttt{red})=1$) and “all vertices must be blue”
($\texttt{count}(c,\texttt{blue})=n$) are symmetric, while “$v$ must be blue”
is asymmetric.

######  Problem 2.8.

(Perfect Matching under Symmetric Vertex-Color constraints, PM-VC-Sym) Does a
graph have a legal perfect matching w.r.t. a symmetric system of constraints?

Figure 2: Left: a DD encoding “the number of red vertices is at least $2$” on
graphs with $4$ vertices. Right: for the graph in Figure 1, all perfect
matchings except the last one are legal w.r.t. to the DD.

###  2.4 Decision Diagram and PM-VC-DD

######  Definition 2.9.

(Decision Diagram) A (reduced, ordered) Decision Diagram (DD), as a
generalization of binary DD (BDD) [9], is a data structure that, in this
paper, encodes a set of vertex colorings as a directed acyclic graph $D$.
There are two terminal nodes with no outgoing edges, expressing True and
False. Each non-terminal node is labeled with a vertex and also has $d$
outgoing edges. Each edge is labeled with a color index in $\\{1,\cdots,d\\}$.
The DD is ordered, i.e., different vertices appear in the same order on all
paths from the root.

Whether a vertex coloring $c:V\to\\{1,\cdots,d\\}$ is legal w.r.t. the DD can
be determined by DD evaluation. The evaluation starts from the unique root of
the DD and at each non-terminal node labeled by $v\in V$, goes through the
edge labeled by $c(v)$ to the next node, until a terminal node is reached. The
coloring is legal iff. the reached terminal node is True.

######  Problem 2.10.

(Perfect Matching under Decision Diagram Vertex-Color constraints, PM-VC-DD)
Does a graph have a legal perfect matching w.r.t. a decision diagram that
encodes legal vertex colorings?

PM-VC-DD is strictly harder than PM-VC-Sym, because 1) systems of symmetric
constraints admit polynomial size DDs [29]; 2) polynomial size DD can encode
asymmetric constraints.

######  Proposition 2.11.

PM-VC-Sym $<_{P}$ PM-VC-DD.

Figure 3: Left: a quantum optical circuit corresponding to the graph in Figure
1. Each crystal (shaded box) correspond to an edge in graph. Each optical path
is converted into a vertex in graph. The modes of photons translate to edge
colors. Right: all PMs in the graph reflect the quantum state of the optical
circuit as a superposition of coincidences. [21]

##  3 Quantum Motivation of PM-VC

This section describes the motivation of PM-VC from quantum-experiment design.
An example of a (simplified) _quantum optical circuit_ is shown in Figure 3
(left). A non-linear _crystal_ (shaded box in Figure 3) can emit a pair of
entangled _photons_ simultaneously if activated by a laser-pump power. Each
photon has a _mode_ , encoded by an integer index. Photons emitted by crystals
travel on _optical paths_. A _receiver_ , which detects the arrival of a
photon and identifies photon mode, is placed at the end of each optical path.
Each crystal is associated with two optical paths [21].

A _coincidence_ of a quantum optical circuit happens when each receiver
detects exactly one photon, due to the activation of some crystals. The
_quantum state_ of a coincidence is the mode of photons caught by all
receivers in the coincidence. The quantum state of an optical circuit is the
_superposition_ [3] of the quantum states of all coincidences.

The optical circuit in Figure 3 (left) has $7$ nonlinear crystals. A
coincidence happens only when crystals in {I,II}, or {I,III}, or {IV,VI} or
{V,VII} are activated simultaneously.

In [21], a coincidence of an optical circuit is shown to be equivalent to a
perfect matching under vertex-color constraints in an undirected graph with
bi-colored edges. The graph $G$ can be constructed as follows. See Figure 3 as
an example.

Each optical path corresponds to a vertex in $G$.

Each crystal corresponds to an edge in $G$. This edge connects two vertices
corresponding to two optical paths which the crystal can emit photons to.

The modes of photons emitted by crystals correspond to edge colors. Since a
crystal can emit two photons with different modes, edges in $G$ are bi-
colored.

A coincidence of an optical circuit corresponds to a perfect matching $P$ in
$G$. The set of edges in $P$ indicates activated crystals. The quantum state
of the coincidence corresponds to the inherited vertex coloring of $P$.

Each crystal has an amplitude as a complex number, corresponding to the edge
weight in graph. The amplitude of a coincidence is the product of the
amplitudes of all activated crystals. The weight of a perfect matching is the
product of weights of all its edges.

A quantum state of an optical circuit can be viewed as a superposition of
coincidences with predefined “legal” quantum states. An optical circuit
exhibits a quantum state if the total amplitude of all coincidences of each
legal states is $1$, while all coincidences with an “illegal” state have total
amplitude $0$ [28]. In the case where only real positive amplitudes are
allowed, a necessary condition of exhibiting a quantum state is the non-
existence of illegal coincidences. In the graph-theoretical setting, the
necessary condition translates to the non-existence of illegal PMs, which can
be refuted by PM-VC algorithms. We list quantum states of interest and their
corresponding vertex-color constraints in Table 1.

Name [20] |  | Quantum state |  | Vertex-color constraints
---|---|---|---|---
GHZ State |  | ${1}/{\sqrt{d}}\cdot\sum_{i=0}^{d-1}\ket{i}^{\oplus n}$ |  | $\bigvee_{i=1}^{d}(\texttt{count}(c,i)=n)$
Dicke State |  | ${1}/{\sqrt{\binom{n}{k}}}\cdot\hat{S}(\ket{0}^{\oplus(n-k)}\ket{1}^{\oplus k})$ |  | $\texttt{count}(c,1)=n-k$
W State |  | ${1}/{\sqrt{n}}\cdot\hat{S}(\ket{0}^{\oplus(n-1)}\ket{1}^{\oplus 1})$ |  | $\texttt{count}(c,1)=n-1$
General Dicke State |  | $1/{\sqrt{\binom{n}{k_{0},\cdots,k_{d-1}}}}\cdot\hat{S}(\ket{0}^{\oplus k_{0}}\cdots\ket{d-1}^{\oplus k_{d-1}})$ |  | $\bigwedge_{i=1}^{d}(\texttt{count}(c,i)=k_{i-1})$
Table 1: Quantum states and their corresponding vertex-color constraints on
perfect matchings.

##  4 Related Work

###  4.1 Quantum Computing Meets Perfect Matching: Krenn’s Conjecture

The connection between constrained PM and quantum computing has been proposed
in a series of works [21, 20, 27]. This line of research has inspired
interesting theoretical open questions recently, e.g., Krenn’s Conjecture on
possible optical circuits that exhibit mono-chromatic GHZ state. While
existing work focused on proving Krenn’s Conjecture in special cases [14] or
verifying it up to a relatively small range [12], investigation of complexity
and algorithmic work for identifying quantum states other than GHZ on large
graphs is lacking.

###  4.2 Matching under Constraints

Previous work has restricted matchings with additional constraints w.r.t. edge
weights and colors. We summarize two lines of research here: exact perfect
matching and constrained maximum matching.

Exact perfect matching (XPM) [19] asks whether there exists a PM that contains
exactly $k$ red edges in a graph with blue/red-colored edges. Strong evidence
of XPM is not NP-hard has been discovered, such as being in RNC and having
good approximation algorithms [43]. Nevertheless, whether XPM is in P still
remains one of the most intriguing open problems in this area, standing open
for more than $40$ years. If one allows a real weight assigned to each edge
and asks for a PM with total weight exactly $W$ (EWPM) [22], the problem is
then NP-hard, though it can be reduced to XPM if all weights are polynomially
bounded.

XPM, known to be in RNC, can be reduced to PM-VC-Sym, meanwhile we prove that
PM-VC-Sym with bounded number of colors is also in RNC in Sec. 5, which
encourages the conjecture that PM-VC-Sym is as hard as XPM. Nevertheless, PM-
VC-Sym appears to be more general than XPM in the sense that 1) there can be
more than two colors 2) bi-colored edges are allowed.

######  Proposition 4.1.

XPM $\leq_{P}$ PM-VC-Sym.

######  Conjecture 4.2.

XPM $=_{P}$ PM-VC-Sym.

XPM can be generalized by allowing more colors. One famous example is rainbow
perfect matching (RPM). Given a graph with $n/2$ edge colors, RPM asks if
there is a PM with all different colors. RPM is NP-hard since it can be
reduced from 3-dimensional perfect matching (3DM), an NP-hard problem. As a
result, PM-VC-Sym becomes NP-hard if the number of colors is no longer
bounded.

######  Proposition 4.3.

PM-VC-Sym with $n/2$ colors is NP-hard because RPM polynomially reduces to it.

On the other hand, bounded color matching (Bounded-CM) [30] and a more general
problem of budget colored matching (Budgeted-CM) [10] assign an integer cost
and weight to each edge. Meanwhile, each color has a budget. The goal is to
find a matching with maximum total weight within the edge color budget. Both
Bounded-CM and Budgeted-CM are proved strongly NP-hard [34] if the number of
colors is unbounded. Multi-budgeted matching [11] further generalizes
Budgeted-CM by additionally assigning each edge a real vector cost and
enforcing linear constraint on maximum matchings, which make the problem
strongly NP-hard even for paths with unbounded number of colors.

In those related problems, either unbounded number of colors or exponential
weighting is necessary for proving NP-hardness. Nevertheless, we show that our
problem, PM-VC-DD is strongly NP-hard even with two colors. From the
perspective of expressiveness, PM-VC subsumes cases of Bounded-CM and
Budgeted-CM where all edges have unit weight and only perfect instead of
maximum matchings are valuable.

##  5 Algorithms for PM-VC-Sym

We show that PM-VC-Sym is in RNC, which can further be derandomized on planar
graphs by Pfaffian orientation. We also present an MSO expression of PM-VC-Sym
and an efficient dynamic programming algorithm on graphs with bounded
treewidth.

###  5.1 Algorithms Based on Symbolic Matrix Determinant

####  5.1.1 Tutte Matrix for PMs in Simple, Uncolored Graphs

We recall the RP algorithm for perfect matching based on Tutte Matrix [31].

######  Definition 5.1.

(Tutte Matrix) [40]The following skew-symmetric matrix $T$ is called the
_Tutte Matrix_ of a graph $G$ 333Here by “graph”, we mean a simple, uncolored
graph., where all $x_{uv}$ are symbols.

$T_{uv}=\begin{cases}x_{uv},&\text{if $(u,v)\in E$ and $u>v$ }\\\
-x_{uv},&\text{if $(u,v)\in E$ and $u<v$ }\\\ 0,&\text{otherwise}\end{cases}$

The most important application of Tutte Matrix is perfect matching.

######  Theorem 5.2.

[40] A graph $G$ has a perfect matching iff. the determinant of its Tutte
matrix is non-zero, i.e., $det(T)\not\equiv 0$.

Symbolic determinant is hard to compute as there can be $O(n!)$ terms in
$det(T)$. However, since by Theorem 5.2 one only needs to know whether
$det(T)$ is non-zero to identify existence of perfect matching, polynomial
identity testing (PIT) can be applied to achieve this goal.

######  Lemma 5.3.

(Schwartz-Zippel Lemma for PIT) [35] Let $F:\mathbb{R}^{n}\to\mathbb{R}$ be a
non-zero polynomial and $S\subset\mathbb{R}$ be a finite set with $|S|>n$. If
we pick a point $a=(a_{1},\cdots,a_{n})$, where each element is sampled
independently and uniformly at random from $S$, then we have
$\mathop{\mathbb{P}}\limits_{a\sim\mathcal{U}[S]^{n}}[F(a)=0]\leq\frac{n}{|S|}.$

There are $|E|$ variables ($x_{uv}$) in $det(T)$ as a polynomial. Therefore,
one can use an integer set with size $c\cdot|E|$ in PIT, where $c$ is a non-
zero constant, to guarantee that if a PM exists, the probability of
identifying it successfully by PIT is at least $1-1/c$. Computing the
determinant of an $n\times n$ numerical matrix can be done in $O(n^{3})$ by
Gaussian Elimination, or in $O(n^{2.37286})$ by the best known matrix
multiplication algorithm [1]. Thus the decision problem of PM in traditional
uncolored graphs is in RP.

####  5.1.2 Adapting Tutte Matrix for Bi-Colored Graphs

Generalizing the symbolic-determinant-based approach for XPM [31], we adapt
Tutte Matrix to non-simple graphs with bi-colored edges, denoted by $A$ in
Definition 5.4. Besides $x_{uv}$, for each color $i\in\\{1,\cdots,d\\}$, we
introduce a symbol $y_{i}$.

######  Definition 5.4.

(Adapted Tutte Matrix) Given a graph $G=(V,E,d)$ with bi-colored edges, we
define the following matrix $A$. For two vertices $u$, $v$, $E_{u,v}$ denotes
the set of all edges connecting $u$ and $v$.

$A_{uv}=\begin{cases}x_{uv}\cdot\sum\limits_{e\in E_{u,v}}y_{c_{u}^{e}}\cdot
y_{c_{v}^{e}},&\text{if $u>v$ }\\\ -x_{uv}\cdot\sum\limits_{e\in
E_{u,v}}y_{c_{u}^{e}}\cdot y_{c_{v}^{e}},&\text{if $u<v$ }\\\
0,&\text{otherwise}\end{cases}$

For example, in the graph shown in Figure 1, we have
$A_{v_{3}v_{4}}=(y_{r}^{2}+y_{r}y_{b})\cdot x_{v_{3}v_{4}}.$

We show in Theorem 5.7 that the approach based on PIT and determinant in Sec.
5.1.1 can be applied to bi-colored graphs by matrix $A$. The key observations
is that, legal PMs w.r.t. symmetric vertex-color constraints correspond to
certain terms in the polynomial representations of $det(A)$.

######  Definition 5.5.

(Legal terms) Let $\mathcal{C}$ be a set of vertex colorings defined by
symmetric constraints, the set of _legal terms_ is defined by
$\mathcal{M}_{\mathcal{C}}=\\{\prod_{i=1}^{d}(y_{i})^{2\cdot\texttt{count}(c,i)}|c\in\mathcal{C}\\}.$

For the example in Figure 2,
$\mathcal{M}_{\mathcal{C}}=\\{y^{8}_{r},y^{6}_{r}y^{2}_{b},y^{6}_{r}y^{2}_{g},y^{4}_{r}y_{b}^{4},y^{4}_{r}y_{g}^{4},y^{4}_{r}y_{b}^{2}y_{g}^{2}\\}$.
Then, analogous to Theorem 5.2, we have the following results.

######  Lemma 5.6.

A graph has a perfect matching in $\mathcal{C}$ defined by symmetric
constraints iff. $det(A)$ has a term in $\mathcal{M}_{\mathcal{C}}$ with non-
zero coefficient.

######  Theorem 5.7.

The decision problem of PM-VC-Sym with $d$ colors can be solved in
$O(\texttt{DET}(n,d)\cdot\log\frac{1}{\epsilon})$ with probability
$1-\epsilon$, where $\texttt{DET}(n,d)$ is the complexity of computing the
symbolic determinant of an $n\times n$ matrix with $d$ symbols.

Obtaining the symbolic determinant can be hard in the worst-case scenario, due
to potential multiplication and division of rational functions. Symbolic
determinant has been shown to be in NC2 [7], indicating that PM-VC-Sym is in
RNC2. Nevertheless, bounding the complexity of $\texttt{DET}(n,d)$ by a
relatively simple algorithm can be non-trivial. We give an upper bound for the
complexity of symbolic determinant by fraction-free Gaussian Elimination [4].

######  Lemma 5.8.

The symbolic polynomial representation of the determinant of an $n\times n$
matrix with $d$ symbols can be solved in $O(n^{2d+1})$ by fraction-free
Gaussian Elimination.

We have shown above that the decision version of PM-VC-Sym is in RNC if the
number of colors is bounded. Nevertheless, it is not straightforward how to
actually obtain such a perfect matching, which is often desirable. An elegant
solution was proposed in [31] for obtaining a PM in XPM, based on isolating
lemma. We extend this approach for obtaining a legal PM in PM-VC-Sym by
proving Theorem 5.9.

######  Theorem 5.9.

There exists a polynomial randomized algorithm such that if a graph has a PM
in the set of legal vertex colorings $\mathcal{C}$ defined by a system of
symmetric constraints, it returns a legal perfect matching with probability at
least $1/2$.

The intuition of the isolating-lemma-based algorithm is, when we randomly
assign integer weights to all edges, there is a good chance that there will be
a unique legal perfect matching with minimum weight, which the search
procedure can focus on.

On planar graphs, the RNC algorithm for PM-VC-Sym based on symbolic
determinant can be derandomized by Pfaffian orientation [38]. A Pfaffian
orientation is an assignment of $\\{\pm 1\\}$ to all symbols $\\{x_{ij}\\}$ in
the Tutte Matrix $T$, such that all terms in $det(T)$ are positive. The high
level idea is, after we evaluate the matrix $A$ on a Pfaffian orientation
deterministically, $G$ has a legal perfect matching iff. $det(A)$ has a legal
term in $\mathcal{M}_{\mathcal{C}}$ with non-zero coefficient. It is shown in
[24] that planar graphs are Pfaffian orientable.

######  Proposition 5.10.

PM-VC-Sym is in NC2 on planar graphs.

###  5.2 A Dynamic Programming Algorithm for Bounded-Treewidth Graphs

Since PM-VC-Sym subsumes XPM, a deterministic polynomial time algorithm for
PM-VC-Sym on general graphs will be a breakthrough for complexity theory.
Nevertheless, progress on special cases of PM-VC-Sym can still be made.
Besides planar graphs, we show that PM-VC-Sym can also be solved
deterministically by dynamic programming (DP) on graphs with bounded
treewidth, encouraged by the MSO expression of PM-VC-Sym.

Treewidth is a graph metric indicating how close a graph is to a tree. Graphs
with bounded treewidth naturally emerge in real-life applications, e.g.,
series/parallel graphs [8], circuit design [42] and machine learning [32].
Treewidth is with algorithmic interest since many graph problems can be solved
in P on bounded treewidth graphs by DP [6].

######  Definition 5.11.

(Tree decomposition and treewidth)  Let G be a graph. Let $\mathcal{T}$ be a
tree where each node of $\mathcal{T}$ is assigned a set of vertices (“bag”) of
$G$. We call $\mathcal{T}$ a _tree decomposition_ of $G$ if the following
holds:

Each edge in $E$ is contained in a bag; that is, if there is an edge
connecting vertices $u,v\in V$, there exists a node of $\mathcal{T}$ whose bag
contains both $u$ and $v$.

The subtree of $\mathcal{T}$ consisting of all bags which contain $u$ is
connected, for all $u\in V$. The width of a tree decomposition $\mathcal{T}$
is defined as (size of largest bag of $\mathcal{T}$) $-1$. The treewidth of a
graph is the minimum width of all its tree decompositions. The treewidth of a
tree is $1$.

Not all graph properties on bounded treewidth graphs can be solved
efficiently. The seminal meta-theorem of Courcelle reveals the deep connection
between monadic second-order logic (MSO) and tractable graph properties on
bounded treewidth graphs. We show that PM-VC-Sym can be expressed in MSO,
which provides strong evidence for the existence of an efficient DP-based
algorithm for PM-VC-Sym on bounded treewidth graphs.

######  Definition 5.12.

(Extended monadic second-order logic (MSO) on graphs) [15] MSO is a fragment
of second-order logic where the second-order quantification is limited to
quantification over sets. The extended MSO allows a graph property to be
expressed by $\\{V,E,\mathbf{edg},\mathbf{Card},P_{1},\cdots,P_{k}\\},$ where
$V$ is the set of vertices; $E$ is the set of (directed) edges;
$\mathbf{edg}_{G}(e,u,v)=\texttt{True}$ iff. there is an edge from $u$ to $v$
in $G$; $\mathbf{Card}_{p,n}(X)\Leftrightarrow|X|\equiv p\mod n$, $X$ is a
subset of $V$ or $E$; $P_{1},\cdots,P_{k}$ are subsets of $V$ or $E$, which
can be viewed as vertices and edge labels/colors.

######  Theorem 5.13.

(Courcelle’s Theorem) [15] Let $f$ be a formula in extended MSO. Then there is
an algorithm which, on every graphs with $n$ vertices and treewidth tw,
decides whether $f$ holds in $G$ in $O(F(|f|,\texttt{tw})\cdot n)$, for some
computable function $F$.

######  Proposition 5.14.

PM-VC-Sym can be expressed in extended MSO with polynomial length.

Therefore, by Courcelle’s theorem, the decision version of PM-VC-Sym problem
can be solved in linear time on bounded-treewidth graphs. However, the
computable function $F$ in Courcelle’s Theorem is often intractable. In this
paper, we propose a concrete DP-based algorithm by proving Theorem 5.15.

######  Theorem 5.15.

PM-VC-Sym on graphs with treewidth bounded by tw can be solved in
$O(n^{2d}(d+1)^{\texttt{tw}+1})$, where $d$ is the number of colors.

######  Proof 5.16.

We first introduce a special type of tree decomposition which is easier to
work with.

######  Definition 5.17.

(Nice tree decomposition) A nice tree decomposition is a tree decomposition
where every node has one of the following four types:

A leaf node has no children and its bag has one vertex.

An introduce node has one child. The child has a bag of same vertices as the
parent with one vertex deleted.

A forget node has one child. The child has a bag of same vertices as the
parent with one vertex added.

A join node has two children, both have a bag identical to the parent’s.

A nice tree decomposition can be obtained from a tree decomposition with
polynomial overhead, as Proposition 5.18 states.

######  Proposition 5.18.

[26] A nice tree decomposition with treewidth tw can be converted from a tree
decomposition with treewidth tw in $O(\texttt{tw}^{2}\cdot n)$ time with
$O(\texttt{tw}\cdot n)$ bags.

In the following we show how to define indicator variables for memoization in
our DP-based procedure. For a node $X$ in the tree decomposition
$\mathcal{T}$, let tree$(X)$ be the set of nodes of the subtree in
$\mathcal{T}$ with root $X$. Let $\texttt{bag}(X)$ be the set of vertices in
$G$ contained in $X$. For a set $S$ of nodes in $\mathcal{T}$, let
$\texttt{bag}(S)$ be $\cup_{X\in S}\texttt{bag}(X)$.

######  Definition 5.19.

(Partial vertex coloring) A partial vertex coloring of a vertex set
$V^{\prime}\subseteq V$ is a mapping from $V^{\prime}$ to
$\\{0,1,\cdots,d\\}$. $c(v)=0$ indicates that $v$ is not matched yet, while
$c(v)=i\in\\{1,\cdots,d\\}$ means $v$ is matched in the graph with inherited
color $i$. A partial vertex coloring $c$ of $V^{\prime}$ is _feasible_ if
there is a matching in the induced graph of $G$ on $V^{\prime}$ whose
inherited partial vertex coloring is $c$.

An indicator Boolean variable in our DP-based algorithm are defined as
$I(X,c,b)$, where $X$ is a node in the nice tree decomposition,
$c:V\to\\{0,1,\cdots,d\\}$ is a partial vertex coloring on $\texttt{bag}(X)$
and $b:\\{1,\cdots,d\\}\to\mathbb{N}$ is a count of colors. Then we define
$I(X,c,b)$ to be true if the partial vertex coloring $c$ of $\texttt{bag}(X)$
can be extended to a _feasible_ partial coloring $c^{\prime}$ of all vertices
in $\texttt{bag}(\texttt{tree}(X))$, such that each color
$i\in\\{1,\cdots,d\\}$ appears exactly $b(i)$ times in $c^{\prime}$.
Otherwise, $I(X,c,b)$ is defined to be False. In our DP-based approach,
$I(X,c,b)$ can be computed recursively as follows:

$X$ is a leaf. Suppose $\texttt{bag}(X)=v$. Set $I(X,\\{c(v)=0\\},0)$ to True.
Set $I(X,c,b)$ to False for all other $c$ and $b$ since the only one node must
be unmatched.

$X$ introduces $v$ from its child $Y$.

  * •

If $c(v)=0$, i.e., $v$ is not matched in the induced subgraph on
$\texttt{bag}(\texttt{tree}(X))$, then $I(X,c,b)=I(Y,c^{\prime},b)$, where
$c^{\prime}(u)=c(u)$ for all $u\in\texttt{bag}(Y)$.

  * •

If $c(v)\neq 0$, i.e., $v$ is matched with some vertices in
$\texttt{bag}(\texttt{tree}(X))$. By Proposition A.8,
$v\not\in\texttt{bag}(\texttt{tree}(Y))$. Therefore, by the definition of tree
decomposition, $\texttt{bag}(Y)$ must contain all $v$’s neighbours in
$\texttt{bag}(\texttt{tree}(X))$. Thus $v$ must be matched with a vertex
$u\in\texttt{bag}(Y)$. Therefore we have
$I(X,c,b)=\bigvee_{u\in\texttt{bag}(Y),c(u)\neq 0,\\{(u,c(u)),(v,c(v))\\}\in
E}I(Y,c^{\prime},b^{\prime})$, where $c^{\prime}(u)=0$ and
$c^{\prime}(w)=c(w)$ for all $w\in\texttt{bag}(Y)-u$;
$b^{\prime}(c(u))=b(c(u))-1$, $b^{\prime}(c(v))=b(c(v))-1$ and
$b^{\prime}(i)=b(i)$ for $i\not\in\\{c(v),c(u)\\}$.

$X$ forgets $v$ from its child $Y$. Since $v$ is forgotten in $X$, it must
have already been matched in $\texttt{bag}(\texttt{tree}(Y))$. Therefore, we
have $I(X,c,b)=\bigvee_{c^{\prime}}I(Y,c^{\prime},b)$ for all $c^{\prime}$
s.t. $c^{\prime}(v)\neq 0$ and $c^{\prime}(w)=c(w)$ for all
$w\in\texttt{bag}(X)$.

X joins its children $Y$ and $Z$. By Proposition A.10, $b$ can be split into
two color counts corresponding to $\texttt{tree}(Y)$ and $\texttt{tree}(Z)$.
Hence we have $I(X,c,b)=\bigvee_{b_{Y},b_{Z}}\big{(}I(Y,c,b_{Y})\wedge
I(Z,c,b_{Z})\big{)}$ for all $b_{Y},b_{Z}:\\{1,\cdots,d\\}\to\mathbb{N}$, s.t.
$b_{Y}(i)+b_{Z}(i)=b(i)+\texttt{count}(c,i)$. Finally, graph $G$ has a legal
PM w.r.t. symmetric constraints iff.
$\bigvee_{b_{l},c}I(\mathcal{T}.\texttt{root},c,b_{l})=\texttt{True}$, for all
$c:\texttt{bag}(\mathcal{T}.\texttt{root})\to\\{1,\cdots,d\\}$ and all legal
count $b_{l}$ w.r.t. the symmetric constraints (note that we have
$\sum_{i\in\\{1,\cdots,d\\}}b_{l}(i)=n$).

Complexity: The time complexity of this DP-based procedure can be bounded by
the product of 1) the number of all possible states of $I$, denoted by $|I|$
and 2) the maximum number of states that one state relies on.

The number of states is given by the product of the following three parts:

number of bags (nodes in the tree decomposition): $O(\texttt{tw}\cdot n)$ by
Proposition 5.18.

number of possible partial colorings $c$: $(d+1)^{\texttt{tw}+1}$.

number of possible count of colors $b$: $\binom{n}{d-1}\sim O(n^{d-1})$.
Therefore the number of all possible states $(X,c,b)$ is $O(\texttt{tw}\cdot
n^{d}\cdot(d+1)^{\texttt{tw}+1})$.

The maximum number of states considered for computing one state is bounded by
the number of possible ways of splitting a count of all colors $b$ at a join
node $X$ into $b_{Y}$ and $b_{Z}$, bounded by
$\prod_{i=1}^{d}(b(i)+1)\leq((\lceil\frac{n}{d}\rceil+1)^{d})\leq(\frac{n+2d}{d})^{d}=O(n^{d})$.
Hence the overall complexity of the DP approach is
$O(n^{2d}(d+1)^{\texttt{tw}+1})$.

######  Corollary 5.20.

The DP-based algorithm solves XPM on bounded-treewidth graphs
deterministically in $O(n^{4}\cdot 3^{\texttt{tw}})$.

##  6 NP-Hardness of PM-VC-DD

We prove that PM-VC-DD with more than $2$ colors is NP-hard, even for special
classes of graphs listed in Corollary 6.3. This result is interesting for two
reasons. First, decision diagrams are considered tractable structures, whose
satisfiability and counting are in polynomial time w.r.t. size of DD [2]. Our
result reveals that when DD is combined with another polynomial problem, i.e.,
PM, the problem PM-VC-DD becomes NP-hard. Second, the NP-hardness of PM-VC-DD
depends on neither exponential weighting nor unbounded number of colors,
unlike other constrained matching problems mentioned in Sec. 4.

######  Theorem 6.1.

PM-VC-DD with number of colors $d\geq 2$ is NP-hard.

######  Proof 6.2.

We reduce 3-SAT to PM-VC-DD with only red-blue monochromatic edges by the
gadget technique, see Figure 4 as an illustration. Suppose
$f=C_{1}\wedge\cdots\wedge C_{m}$ is an arbitrary 3-CNF formula with variable
set $X$, where each $C_{i}(1\leq i\leq m$) is a clause with $3$ literals.

Graph construction: For each clause $C_{i}=l_{i,1}\vee l_{i,2}\vee l_{i,3}$,
we construct a gadget consisting of 6 vertices: 1 vertex $u_{i}$ representing
the clause, 3 vertices $v_{i,1}$, $v_{i,2}$, $v_{i,3}$ representing the three
literals in the clause and 2 dummy vertices $w_{i,1}$ and $w_{i,2}$.

Figure 4: An example of reducing a 3-CNF formula to a graph in PM-VC-DD.

There is an edge that connects each vertex $v_{i,k}$ ($k=1,2,3$) corresponds
to a literal with the vertex $u_{i}$ corresponding to clause $C_{i}$. Each
edge between $v_{i,k}$ to $u_{i}$, is colored red if the literal $l_{i,k}$ is
positive in $C_{i}$. Otherwise the edge is colored blue. There is one blue and
one red edge connecting each dummy vertex $w_{i,k}$ ($k=1,2$) and each vertex
representing the literal $v_{i,k}$ ($k=1,2,3$). The graph $G$ is the union of
gadgets corresponding to all clauses.

DD construction: For each variable $x\in X$, we denote by $V^{x}$ the set of
all vertices of $G$ that corresponds to $x$. The DD $D$ in our reduction is
the conjunction of DDs of the mono-chromatic constraint for each variable
$x\in X$, i.e., all vertices in $V_{x}$ have the same color. Since there are
only two colors in our reduction, a binary DD (BDD) is constructed.

Correctness of the reduction: we need to prove:

The graph $G$ has a perfect matching with inherited vertex coloring satisfying
the binary DD $D$ iff. the 3-CNF formula $f$ is satisfiable.

The reduction is polynomial. The graph $G$ is with polynomial size since it
has $6\cdot m$ vertices where $m$ is # clauses of $f$. We need to show that
there exists a binary DD $D$ with polynomial size that represents the
conjunction of color constraints. Moreover, $D$ needs to be constructed in
polynomial time.

Proof of (1): $\Leftarrow$: Suppose the 3-CNF formula is satisfiable and
$s:X\to\\{\texttt{True},\texttt{False}\\}$ is a solution. We construct a legal
perfect matching $P$ w.r.t. $D$. For each clause $C_{i}$, there is at least
one literal whose assignment in $s$ satisfies the clause. Without loss of
generality, suppose $l_{i,1}$ satisfies the clause. Then we add the edge
between $v_{i,1}$ to $u_{i}$ into the matching $P$. By the construction of the
graph $G$, the color of this edge is red if $l_{i,1}$ is assigned True in $s$
and blue if $l_{i,1}$ is assigned False in $s$. For the two vertices
corresponding the rest two literals in the clause, i.e., $v_{i,2}$ and
$v_{i,3}$, we match them with two dummy vertices $w_{i,1}$ and $w_{i,2}$. For
example, we add to $P$ an edge between $v_{i,2}$ and $w_{i,1}$, whose color is
red if the variable of $l_{i,2}$ is assigned True in $s$ and blue if $l_{i,2}$
is assigned False in $s$. We add an edge to $P$ between $v_{i,3}$ and
$w_{i,2}$ similarly. All 6 vertices in the gadget of clause $i$ is perfectly
matched. Therefore $P$ is a perfect matching of $G$. We need to prove that our
perfect matching $P$ is legal w.r.t. the DD $D$. Due to the construction of
$P$, for each variable $x$, the inherited color of vertices in $V^{x}$ w.r.t.
$P$ must be the same, which is determined by the unique assignment of $x$ in
the solution $s$. This is exactly what $D$ encodes. Hence $P$ is legal w.r.t.
$D$.

$\mathbf{\Rightarrow}$: Suppose graph $G$ has a legal perfect matching $P$
w.r.t. $D$. Then we construct an assignment
$s:X\to\\{\texttt{True},\texttt{False}\\}$ from $P$ and show that $s$ is a
solution of $f$. Since $P$ is legal w.r.t. $D$, the inherited color of all
vertices in $V^{x}$ must be the same for all $x\in X$. For each variable $x$,
$s(x)=\texttt{True}$ if the inherited color of all vertices in $V^{x}$ w.r.t.
$P$ is red and $s(x)=\texttt{False}$ otherwise. We show that $s$ is a
solution. For each clause $C_{i}$, since its corresponding gadget is perfectly
matched in $P$, the vertex $u_{i}$ must be connected with a vertex
corresponding to one of the three literals, say $l_{i,1}$. This implies that
literal $l_{i,1}$ is satisfied by $s$ and so is clause $C_{i}$. Hence $s$ is a
solution of formula $f$ and $f$ is satisfiable. ∎

Proof of (2): $D$ is the conjunction of “the color of all vertices in $V_{x}$
are equal” for all $x\in X$, which is an All-Equal constraint. It is well
known that as a symmetric Boolean function, an All-Equal constraint admits a
polynomial size DD [29]. We denote the DD of the All-Equal constraint
regarding $x$ as $D_{x}$. In addition, note that for two variables
$x_{1},x_{2}\in X$, we have $V_{x_{1}}\cap V_{x_{2}}=\emptyset$. A DD
representing $D_{x_{1}}\wedge D_{x_{2}}$ with size
$O(|D_{x_{1}}|+|D_{x_{2}}|)$ can be constructed in polynomial time. This is
done simply by substituting $D_{x_{1}}.\texttt{True}$ by $D_{x_{2}}$ (note
that $D_{x_{1}}$ and $D_{x_{2}}$ do not share variables). Thus a DD
representing $\bigwedge_{x\in X}D_{x}$ with polynomial size can be constructed
in polynomial time and the reduction is polynomial.

######  Corollary 6.3.

From the constructive proof of Theorem 6.1, PM-VC-DD on the following special
classes of graphs is still NP-hard: 1) Graphs with bounded treewidth $\geq 3$.
2) Non-simple bipartite graphs. 3) Graphs with only mono-chromatic edges.

##  7 Conclusions and Future Directions

In this paper, we proposed and studied the problem of perfect matching under
vertex-color constraints (PM-VC). We prove that PM-VC with symmetric vertex-
color constraint is in RNC and expressible in extended MSO. On planar and
bounded-treewidth graphs, PM-VC-Sym is in P. We also give negative theoretical
results on PM-VC with decision diagram constraint. The problem is inspired
from quantum computing and our results shed light on understanding the
complexity of testing quantum states of large quantum optical circuits.

Our work leaves interesting open questions and future directions. For example,
is PM-VC-Sym as hard as XPM? On which other special graphs can PM-VC be solved
efficiently? Are there more interesting types of vertex-color constraints?
Motivated by leveraging classical algorithms in the development of quantum
computing, we plan to design scalable algorithms for PM-VC and matching
partition functions [5]. Besides PM, we also expect to tackle other quantum-
inspired classical problems by combinatorial and logical approaches.

## References

  * [1] Josh Alman and Virginia Vassilevska Williams.  A refined laser method and faster matrix multiplication.  In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522–539. SIAM, 2021.
  * [2] Henrik Reif Andersen.  An introduction to binary decision diagrams.  Lecture notes, available online, IT University of Copenhagen, page 5, 1997.
  * [3] Leslie E Ballentine.  Quantum mechanics: a modern development.  World Scientific Publishing Company, 2014.
  * [4] Erwin H Bareiss.  Sylvester’s identity and multistep integer-preserving gaussian elimination.  Mathematics of computation, 22(103):565–578, 1968.
  * [5] Alexander Barvinok and Alex Samorodnitsky.  Computing the partition function for perfect matchings in a hypergraph.  Combinatorics, Probability and Computing, 20(6):815–835, 2011.
  * [6] Hans L Bodlaender.  Dynamic programming on graphs with bounded treewidth.  In International Colloquium on Automata, Languages, and Programming, pages 105–118. Springer, 1988.
  * [7] Allan Borodin, Stephen Cook, and Nicholas Pippenger.  Parallel computation for well-endowed rings and space-bounded probabilistic machines.  Information and control, 58(1-3):113–136, 1983.
  * [8] Andreas Brandstädt, Van Bang Le, and Jeremy P Spinrad.  Graph classes: a survey.  SIAM, 1999.
  * [9] Randal E Bryant.  Symbolic boolean manipulation with ordered binary-decision diagrams.  ACM Computing Surveys (CSUR), 24(3):293–318, 1992.
  * [10] Christina Büsing and Martin Comis.  Budgeted colored matching problems.  Electronic Notes in Discrete Mathematics, 64:245–254, 2018.
  * [11] Christina Büsing and Martin Comis.  Multi-budgeted matching problems.  Networks, 72(1):25–41, 2018.
  * [12] Alba Cervera-Lierta, Mario Krenn, and Alán Aspuru-Guzik.  Design of quantum optical experiments with logic artificial intelligence.  arXiv preprint arXiv:2109.13273, 2021.
  * [13] Chekuri Chandra, Lai Tin-Yin, and Andrews Robert.  Matchings via determinants (lecture notes).  Technical report, UIUC.
  * [14] L Sunil Chandran and Rishikesh Gajjala.  Perfect matchings and quantum physics: Progress on krenn’s conjecture.  arXiv preprint arXiv:2202.05562, 2022.
  * [15] Bruno Courcelle.  The monadic second-order logic of graphs. i. recognizable sets of finite graphs.  Information and computation, 85(1):12–75, 1990.
  * [16] David Deutsch.  Quantum theory, the church–turing principle and the universal quantum computer.  Proc, Royal Society of London. A. Mathematical and Physical Sciences, 400(1818):97–117, 1985.
  * [17] Ross Duncan, Aleks Kissinger, Simon Perdrix, and John Van De Wetering.  Graph-theoretic simplification of quantum circuits with the zx-calculus.  Quantum, 4:279, 2020.
  * [18] Jack Edmonds.  Paths, trees, and flowers.  Canadian Journal of mathematics, 17:449–467, 1965.
  * [19] Nicolas ElMaalouly.  Exact matching: Algorithms and related problems.  arXiv preprint arXiv:2203.13899, 2022.
  * [20] Xuemei Gu, Lijun Chen, Anton Zeilinger, and Mario Krenn.  Quantum experiments and graphs. iii. high-dimensional and multiparticle entanglement.  Physical Review A, 99(3):032338, 2019.
  * [21] Xuemei Gu, Manuel Erhard, Anton Zeilinger, and Mario Krenn.  Quantum experiments and graphs ii: Quantum interference, computation, and state generation.  Proceedings of the National Academy of Sciences, 116(10):4147–4155, 2019.
  * [22] Rohit Gurjar, Arpita Korwar, Jochen Messner, Simon Straub, and Thomas Thierauf.  Planarizing gadgets for perfect matching do not exist.  In International Symposium on Mathematical Foundations of Computer Science, pages 478–490. Springer, 2012.
  * [23] Hossein Z Jooya, Kamran Reihani, and Shih-I Chu.  A graph-theoretical representation of multiphoton resonance processes in superconducting quantum circuits.  Scientific Reports, 6(1):1–10, 2016.
  * [24] Pieter Kasteleyn.  Graph theory and crystal physics.  Graph theory and theoretical physics, pages 43–110, 1967.
  * [25] Tanya Khovanova and Ziv Scully.  Efficient calculation of determinants of symbolic matrices with many variables.  arXiv preprint arXiv:1304.4691, 2013.
  * [26] Ton Kloks.  Treewidth: computations and approximations.  Springer, 1994.
  * [27] Mario Krenn, Xuemei Gu, and Daniel Soltész.  Questions on the structure of perfect matchings inspired by quantum physics.  arXiv preprint arXiv:1902.06023, 2019.
  * [28] Mario Krenn, Xuemei Gu, and Anton Zeilinger.  Quantum experiments and graphs: Multiparty states as coherent superpositions of perfect matchings.  Physical review letters, 119(24):240403, 2017.
  * [29] Anastasios Kyrillidis, Moshe Vardi, and Zhiwei Zhang.  On continuous local bdd-based search for hybrid sat solving.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 3841–3850, 2021.
  * [30] Monaldo Mastrolilli and Georgios Stamoulis.  Bi-criteria and approximation algorithms for restricted matchings.  Theoretical Computer Science, 540:115–132, 2014.
  * [31] Ketan Mulmuley, Umesh V Vazirani, and Vijay V Vazirani.  Matching is as easy as matrix inversion.  In Proceedings of the nineteenth annual ACM symposium on Theory of computing, pages 345–354, 1987.
  * [32] Mukund Narasimhan and Jeff A Bilmes.  Pac-learning bounded tree-width graphical models.  arXiv preprint arXiv:1207.4151, 2012.
  * [33] Jian-Wei Pan, Zeng-Bing Chen, Chao-Yang Lu, Harald Weinfurter, Anton Zeilinger, and Marek Żukowski.  Multiphoton entanglement and interferometry.  Reviews of Modern Physics, 84(2):777, 2012.
  * [34] Irena Rusu.  Maximum weight edge-constrained matchings.  Discrete applied mathematics, 156(5):662–672, 2008.
  * [35] Nitin Saxena.  Progress on polynomial identity testing.  Bull. EATCS, 99:49–79, 2009.
  * [36] Peter W Shor.  Algorithms for quantum computation: discrete logarithms and factoring.  In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. Ieee, 1994.
  * [37] Daniel R Simon.  On the power of quantum computation.  SIAM journal on computing, 26(5):1474–1483, 1997.
  * [38] Robin Thomas.  A survey of pfaffian orientations of graphs.  In Proceedings of the International Congress of Mathematicians, volume 3, pages 963–984. Citeseer, 2006.
  * [39] Peter R Turner.  Gauss elimination: Workhorse of linear algebra.  Technical report, NAVAL AIR WARFARE CENTER AIRCRAFT DIV PATUXENT RIVER MD, 1995.
  * [40] William T Tutte.  The factorization of linear graphs.  Journal of the London Mathematical Society, 1(2):107–111, 1947\.
  * [41] Leslie G Valiant and Vijay V Vazirani.  Np is as easy as detecting unique solutions.  In Proceedings of the seventeenth annual ACM symposium on Theory of computing, pages 458–463, 1985.
  * [42] Dong Wang, Edmund Clarke, Yunshan Zhu, and James Kukula.  Using cutwidth to improve symbolic simulation and boolean satisfiability.  In Sixth IEEE International High-Level Design Validation and Test Workshop, pages 165–170. IEEE, 2001.
  * [43] Raphael Yuster.  Almost exact matchings.  Algorithmica, 63(1):39–50, 2012.

##  Appendix A Appendix

###  A.1 Technical Proofs

####  A.1.1 Proof of Proposition 2.6

When $|\mathcal{C}|$ is polynomial, PM-VC can be solved by calling the
following procedure for each vertex coloring $c\in\mathcal{C}$.

Given a vertex color $c$, let $G_{c}$ be the subgraph with the original vertex
set $V$ but a subset of edges, selected as follows:

$E_{c}=\\{c_{u}^{e}=c(u),c_{u}^{e}=c(v)|\\{(u,c_{u}^{e}),(v,c_{v}^{e})\\}\in
E\\}$

That is, in $G_{c}$, we only keep the edges whose colors agree with the vertex
coloring $c$. Then we run a polynomial algorithm $\mathcal{A}$ for perfect
matching on uncolored graphs, say Blossom Algorithm. In the following we prove
that the original graph $G$ has a perfect matching whose inherited vertex
coloring is $c$ iff. $\mathcal{A}$ returns True.

$\Rightarrow:$ If there is a PM $P$ whose inherited vertex coloring is $c$,
then every edge of $P$ must be in $E_{c}$. Therefore $G_{c}$ has an uncolored
perfect matching and $\mathcal{A}$ returns True.

$\Leftarrow:$ Suppose $\mathcal{A}$ returns True, which means $G_{c}$ has an
uncolored PM $P$. Then the colors of every edge in $P$ agree with $c$, which
indicates $G$ has a perfect matching with inherited color $c$.

Therefore, the answer for the decision version of PM-VC is True iff.
$\mathcal{A}$ returns True for at least one vertex coloring $c\in\mathcal{C}$.
∎

####  A.1.2 Proof of Proposition 4.2

We reduce XPM to PM-VC-Sym with only monochromatic edges. The graph $G$ in PM-
VC-Sym remains the same. We only need to transform the cardinality constraint
of edge colorings to a system of symmetric vertex-color constraints. Since all
edges are monochromatic, the set of perfect matchings with $k$ red edges is
equal to the set of perfect matchings with $2k$ red vertices in their
inherited vertex coloring. Clearly this reduction is polynomial. ∎

####  A.1.3 Proof of Lemma 5.6

$\Leftarrow:$ Suppose $G$ has a perfect matching $P$ whose inherited vertex
coloring $c$ is in $S$. We have that $|V|=n$ is even. Given perfect matching
$P$ with each edge and (arbitrarily) ordered pair $(u,v)$. Set $x_{uv}=1$ if
$\\{(u,c(u)),(v,c(v))\\}\in P$ and $u>v$. Otherwise set $x_{uv}=0$. Let $\pi$
be a permutation such that for each $\\{(u,c(u)),(v,c(v))\\}\in P$ we have
$u=\pi(v)$ and $v=\pi(u)$. Now consider the term $\prod_{i=1}A_{i\pi(i)}$ of
$det(A)$. It is clearly equal to $\prod_{i}y_{i}^{2\cdot c(i)}$. Moreover, all
other terms are zero, therefore $det(A)\neq 0$.

$\Rightarrow:$ Note that a permutation $\pi$ can be decomposed into a
collection of cycles where each element exchanges places with the next. Any
permutation on $n$ elements can be uniquely expressed as a collection of
disjoint cycles. Suppose permutation $\pi$ has odd cycle
$\sigma=(i_{1},i_{2},\cdots,i_{r})$, i.e $r$ is odd, so that
$i_{k+1}=\pi(i_{k})$. Consider permutation $\pi^{\prime}$ which is the same as
permutation except that the cycle $\sigma$ is reversed, i.e.
$i_{k}=\pi^{\prime}(i_{k+1})$. It is not hard to check that

$sgn(\pi)\prod^{n}_{i=1}A_{i\pi(i)}=-sgn(\pi)\prod_{i=1}^{n}A_{i\pi^{\prime}(i)}$

since we negate an odd number of terms in the product corresponding to
$\pi^{\prime}$ by definition of skew-symmetric $A$ but the sign of the two
permutations remains the same. Then when evaluating $det(A)$ we note that
permutations with odd cycles cancel out. Thus since $det(A)$ has a non-zero
term in $M$, $A$ must have a permutation whose corresponding cycle
decomposition consists only of even cycles. Note that each such cycle
corresponds to a perfect matching over the vertices in it. Each color $i$
appears in the inherit vertex coloring of this matching exactly $c(i)$ times.
∎

####  A.1.4 Proof of Theorem 5.7

The following is an RP algorithm for PM-VC-Sym:

Construct the symbolic matrix $A$ from graph $G$ by Definition 5.4.

Choose the set size $2|E|$ and conduct PIT on $det(A)$.

If there exists a term in the polynomial of $det(A)$ in $\mathcal{M}$ with
non-zero coefficient, return “yes”, otherwise return “no”. If $G$ has no legal
perfect matching, then after PIT in (2), (3) always returns “no”. If there
exists at least one legal PM, then the algorithm above gives “yes” with
probability at least $1/2$. Therefore by $O(\log\frac{1}{\epsilon})$
independent runs of this algorithm, we get the correct answer to PM-VC-Sym
with probability at least $1-\epsilon$. ∎

####  A.1.5 Proof of Lemma 5.8

The fraction-free Gaussian Elimination [4] for computing the determinant of a
matrix $a$ computes a sequence of matrix $a^{k}$, where $a^{1}=a$ and

$a_{ij}^{k+1}=\frac{a_{kk}^{k}a_{ij}^{k}-a_{ik}^{k}a_{kj}^{k}}{a^{k-1}_{k-1,k-1}},\,\,\,\,i,j\in\\{k+1,\cdots,n\\}\times\\{k,\cdots,n\\}$

and $a_{00}^{0}$ is defined to be $0$. After all the computations,
$a_{nn}^{n}$ is the determinant of $a$.

It is proven that each term computed by the equation above is fraction-free,
i.e., $a^{k-1}_{k-1,k-1}$ is a factor of
$a_{kk}^{k}a_{ij}^{k}-a_{ik}^{k}a_{kj}^{k}$. The procedure requires $O(n^{3})$
polynomial multiplications and divisions [25]. Multiplying or devising two
polynomials $p,q$ takes $O(T(p)T(q))$, where $T(p)$ is the number of terms in
$p$.

######  Lemma A.1.

Let $A$ be the matrix defined in Definition 5.4 and $A_{ij}^{k}$ be an element
computed in fraction-free Gaussian Elimination of $A$. Then $A_{ij}^{k}$ is
either $0$ or homogeneous of degree $2k$.

######  Proof A.2.

We prove by induction.

Basis: when $k=1$ the statement holds since every term in $A$ is either $0$ or
a homogeneous polynomial with degree $2$.

Inductive step: suppose each $A_{ij}^{k}$ ($k\geq 1$) is either $0$ or a
homogeneous polynomial of degree $2k$. Then

$A_{ij}^{k+1}=\frac{A_{kk}^{k}A_{ij}^{k}-A_{ik}^{k}A_{kj}^{k}}{A^{k-1}_{k-1,k-1}}$

By inductive hypothesis, $A_{kk}^{k}A_{ij}^{k}-A_{ik}^{k}A_{kj}^{k}$ is either
$0$ or homogeneous with degree $2k+2k=4k$. It was proved in [39] that
$A^{k}_{kk}$ is the determinant of the primal minor of $A$ of dimension $k$
for all $k$. Therefore $A^{k-1}_{k-1,k-1}$ is non-zero and must be homogeneous
of degree $2k-2$, by inductive hypothesis. Since $A_{k-1}A_{k-1}^{k-1}$
divides $A_{kk}^{k}A_{ij}^{k}-A_{ik}^{k}A_{kj}^{k}$, we have $A_{ij}^{k+1}$ is
either $0$ or homogeneous of degree $4k-(2k-2)=2(k+1)$, which completes the
proof.

Back to the proof of Lemma 5.8, all polynomials during the fraction-free
Gaussian elimination are either $0$ or homogeneous polynomials of degree $2n$.
Therefore, the cost of multiplying or devising two polynomials is bounded by
$O(n^{2d-2})$. Hence the complexity of symbolic determinant of $A$ by
fraction-free Gaussian Elimination is bounded by $O(n^{2d-2}\cdot
n^{3})=O(n^{2d+1})$. ∎

####  A.1.6 Proof of Theorem 5.9 (Obtaining a Perfect Matching)

Some proofs in this section are adapted from [13] for handling PM-VC-Sym.

######  Definition A.3.

(Set system) A set system $(S,F)$ consists of a finite set S of elements,
$s=\\{x_{1},x_{2},\cdots,x_{n}\\}$, and a family $F$ of subsets of $S$, i.e.
$F={S_{1},S_{2},\cdots,S_{k}}$, $S_{j}\subseteq S$, for $1\leq j\leq k$.

Let us assign a weight $w_{i}$ to each element $X_{i}\in S$ and let us define
the weight of the set $S_{j}$ to be $\sum_{x_{i}\in S_{j}}w_{i}$. Then the
isolation lemma is as follows:

######  Lemma A.4.

(Isolating Lemma) [41] Let $(S,F)$ be a set system whose elements are assigned
integer weights chosen uniformly and independently from $\\{1,2,\cdots,K\\}$,
Then,

$\mathbb{P}[\text{There is a unique minimum weight set in
$F$}]\geq\frac{n}{K}$

In our case, the set system consists of $|E|$ edges as elements, while all
perfect matchings that satisfy the symmetric constraints form the system. We
assign random integer weights from $\\{1,\cdots,2\cdot|E|\\}$ to all edges.
Suppose the weight assigned to edge $(i,j)$ is $w_{ij}$. We have the following
modification to the matrix $A$ to get matrix $B$:

$B_{uv}=\begin{cases}\sum\limits_{e\in E_{u,v}}y_{c_{u}^{e}}\cdot
y_{c_{v}^{e}}\cdot 2^{w_{e}},&\text{if $u>v$ }\\\ \sum\limits_{e\in
E_{u,v}}y_{c_{u}^{e}}\cdot y_{c_{v}^{e}}\cdot(-2^{w_{e}}),&\text{if $u<v$ }\\\
0,&\text{otherwise}\end{cases}$

Let the weight of each perfect matching $P$ be $\sum_{e\in P}w_{e}$.

######  Lemma A.5.

If graph $G$ has a legal perfect matching, then with probability at least
$\frac{1}{2}$ there exists a term in $det(B)$ with non-zero coefficient $p$.
The highest power of $2$ that divides $p$ is $2^{2W}$, where $W$ is the weight
of the legal perfect matching with minimum weight.

######  Proof A.6.

Recall that terms corresponding to permutations with odd cycles cancel out.
For the permutation $\sigma$ corresponding to the unique legal minimum-weight
perfect matching in $G$, we have $\prod_{i=1}B_{i,\sigma(i)}=\pm 2^{2W}$ . We
will show that for all other permutations $\tau$, we have
$\prod_{i=1}T_{i,\tau(i)}=\pm 2^{2W^{\prime}}$ for some integer $a>W$, which
completes the proof. Let $\tau$ be a permutation not corresponding to the
unique legal minimum-weight perfect matching in $G$. If $\tau$ corresponds to
a legal matching of weight $W^{\prime}$, then $\prod_{i=1}B_{i,\tau(i)}=\pm
2^{2W^{\prime}}$. Since this matching is not the one of minimum-weight, we
have $W>W^{\prime}$ as required. Suppose instead that $\tau$ is a permutation
consisting solely of even cycles, but not necessarily corresponding to a
matching in $G$. Suppose that $\prod_{i=1}B_{i,\tau(i)}=\pm 2^{2W^{\prime}}$
with $W^{\prime}\leq W$. Then we show that a legal perfect matching with
weight $W^{\prime}$ can be constructed from $\tau$, which conflicts with the
assumption that there is a unique legal perfect matching with weight $W$. For
each even circle $\mathcal{C}$, one can construct two matchings that cover all
vertices in $\mathcal{C}$. We choose the one with lower weight. The matchings
from all even circles forms a legal perfect matching of $G$, with weight $\leq
W$.

After obtaining the weight $W$ of the legal PM $P$ with minimum weight, for
each edge $e$, whether it is in the PM $P$ can be determined by the following
lemma.

######  Lemma A.7.

[31] For each edge $e\in E$, $e$ belongs to the legal perfect matching iff.
$\frac{det(B_{ij})}{2^{W-w_{e}}}$ is odd.

Therefore, a legal perfect matching can be obtained by a randomized algorithm
in polynomial time. ∎

####  A.1.7 Proof of Proposition 5.10

Since the graph $G$ is planar, we can evaluate the matrix $A$ in Definition
5.4 at the Pfaffian Orientation of $G$ [24]. The Pfaffian Orientation
evaluates every term in $det(A)$ to be positive. By similar argument in the
proof of Lemma 5.6, graph $G$ has a legal PM iff. the evaluation of $det(A)$
at the Pfaffian Orientation has a term in $\mathcal{M}_{\mathcal{C}}$. Since
the evaluation of symbolic determinant is in NC2 [7], PM-VC-Sym on planar
graphs is also in NC2. ∎

####  A.1.8 Proof of Proposition 5.14 (Monadic second-order logic)

We show that PM-VC-Sym can be expressed in extended Monadic second-order logic
(MSO) with cardinality predicates. I.e., we show the MSO representation of PM-
VC-Sym on graph $G$ with bi-colored edges. To represent possibly two colors on
one edge, we view all edges in $G$ as directed edges, while the direction can
be arbitrary. Then, for each color, we define two edge sets $E_{tail}^{i}$ and
$E_{head}^{i}$ as follows:

$E_{head}^{i}=\\{e=(u,v)\in E|\text{the color of $e$ at $u$ is $i$}\\},$

$E_{tail}^{i}=\\{e=(u,v)\in E|\text{the color of $e$ at $v$ is $i$}\\}.$

For the sake of simplicity, we define the adjacent relations between a vertex
and an edge by the predicate $\mathbf{edg}$:

$head(v,e)=\exists u\in V,\mathbf{edg}(e,v,u),$

$tail(v,e)=\exists u\in V,\mathbf{edg}(e,u,v),$

$adj(v,e)=head(v,e)\vee tail(v,e).$

For two edges, we define a predicate indicating whether two edges share a
vertex:

$overlap(e_{1},e_{2})=\exists v\in V,adj(v,e_{1})\wedge adj(v,e_{2}).$

Then the MSO2 formula of PM-VC-Sym is:

$\exists V_{1}V_{2}\cdots V_{d}\subseteq V,P\subseteq
E,\texttt{INDEPENDENT}\wedge\texttt{COLOR}\wedge\texttt{CARD},$

where

$\texttt{INDEPENDENT}=\forall e_{1},e_{2}\in P,\neg overlap(e_{1},e_{2})$
$\texttt{COLOR}=(\forall v\in V,\exists e\in
P,(adj(v,e))\wedge\big{(}\bigwedge_{i}(v\in V_{i})\to\big{(}(head(v,e)\to e\in
E_{head}^{i})\wedge(tail(v,e)\to e\in E_{tail}^{i})\big{)}\big{)}$

$\texttt{CARD}=\bigwedge_{i}Card_{d_{i},n}(V_{i})$

∎

####  A.1.9 Auxiliary Propositions for Proving Theorem 5.15

######  Proposition A.8.

On a node $X$ that introduces $v$ with child $Y$,
$v\not\in\texttt{bag}(\texttt{tree}(Y))$.

######  Proof A.9.

Suppose $v\in\texttt{bag({Y})}$. Since $X$ introduces $v$,
$v\not\in\texttt{bag}(Y)$. Therefore $v$ must appear in the bag of a node $Z$,
which is separated from $X$ by $Y$. This contradicts with the second condition
in the definition of tree decomposition.

######  Proposition A.10.

On a join node $X$ with children $Y$, $Z$,
$\texttt{bag}(X)=\texttt{bag}(\texttt{Tree}(Y))\cap\texttt{bag}(\texttt{Tree}(Z))$.

######  Proof A.11.

We first prove that for each vertex $v$ in both
$\texttt{bag}(\texttt{Tree}(Y))$ and $\texttt{bag}(\texttt{Tree}(Z))$,
$v\in\texttt{bag}(X)$. Suppose there exists a vertex
$v\in\texttt{bag}(\texttt{Tree}(Y))\cap\texttt{bag}(\texttt{Tree}(Z))$ but
$v\not\in\texttt{bag}(X)=\texttt{bag}(Y)=\texttt{bag}(Z)$. Then there exist a
node $Y^{\prime}\in\texttt{Tree}(Y)$ and a node
$Z^{\prime}\in\texttt{Tree}(Y)$ such that $v\in\texttt{bag}(Y^{\prime})$ and
$v\in\texttt{bag}(Z^{\prime})$. However, $Y^{\prime}$ and $Z^{\prime}$ are
separated by $X$, which violates the second condition in the definition of
nice tree decomposition.

Next we show that if a vertex $v$ is in $\texttt{bag}(X)$, then $v$ must be in
$\texttt{bag}(\texttt{Tree}(Y))\cap\texttt{bag}(\texttt{Tree}(Z))$. Since $X$
is a join node, we have $\texttt{bag}(X)=\texttt{bag}(Y)=\texttt{bag}(Z)$ and
the statement holds trivially.


# Related Problems in Spherical and Solid Geometry

Michael Q. Rieck111Drake University, Math & CS Dept., Des Moines, IA 50310,
USA<EMAIL_ADDRESS>
( )

###### Abstract

A problem that is simple to state in the context of spherical geometry, and
that seems rather interesting, appears to have been unexamined to date in the
mathematical literature. The problem can also be recast as a problem in the
real projective plane. The problem on the sphere involves four great circles
and their intersections. A substantial claim is made concerning this problem,
and subsequently proved by relating the spherical problem to a compelling
problem in solid geometry. This latter problem essentially concerns
relationships between the angles of a tetrahedron, and has practical
applications, particularly in connection with the Perspective 3-Point (Pose)
Problem.

AMS subject classification: 51M15, 51N20, 52B10, 51N15, 51M10

keywords: spherical geometry, solid geometry, tetrahedron, projective plane,
elliptic plane.

##  1 A problem in spherical geometry

Figure 1: The spherical geometry problem

The problem considered in this section is concerned with great circles on the
unit sphere. It begins with six positive numbers, $\angle A$, $\angle B$,
$\angle C$, $\alpha$, $\beta$, and $\gamma$, subject to these restrictions:
$\angle A+\angle B+\angle C=\pi$, $\alpha+\beta+\gamma<2\pi$,
$\alpha<\beta+\gamma$, $\beta<\gamma+\alpha$ and $\gamma<\alpha+\beta$. The
notation “$\angle A$” is not here meant to imply the existence of a point
“$A$,” and so forth. This notation will be justified in the next section. All
angles will be measured in radians.

Consider any three great circles, with three arcs, one from each circle,
forming a spherical triangle with side lengths $\alpha$, $\beta$ and $\gamma$.
The constraints on the numbers $\alpha$, $\beta$ and $\gamma$ ensure that such
circles exist. The circle with the arc of length $\alpha$ (resp, $\beta$,
$\gamma$) will be denoted $\mathscr{C}_{1}$ (resp. $\mathscr{C}_{2}$,
$\mathscr{C}_{3}$). For another arbitrary great circle $\mathscr{C}$, let
$p_{j}$ and $p^{\prime}_{j}$ denote the intersection points of $\mathscr{C}$
and $\mathscr{C}_{j}$ ($j=1,2,3$). Without loss of generality, moving around
$\mathscr{C}$ (in one of the two directions), assume that the six intersection
points occur in this cyclic order:
$p_{1},p_{2},p_{3},p^{\prime}_{1},p^{\prime}_{2},p^{\prime}_{3}$. See Figure
1. Now ask the following.

Question 1. Does there exist a great circle $\mathscr{C}$ along which the arcs
from $p_{1}$ to $p_{2}$, from $p_{2}$ to $p_{3}$, and from $p_{3}$ to
$p^{\prime}_{1}$, have lengths $\angle C$, $\angle A$ and $\angle B$,
respectively?

There is a comparatively simple case with a very simple answer, as follows.

######  Proposition 1.

If $\angle A$, $\angle B$ and $\angle C$ do not exceed $\pi/2$, then Question
1 is answered in the affirmative.

Before proving this claim, the question posed here will be shown to be
equivalent to a different question in three-dimensional real space.

##  2 A problem in solid geometry

We continue to assume that numbers $\angle A$, $\angle B$, $\angle C$,
$\alpha$, $\beta$, and $\gamma$, as in the previous section, have been fixed.
Let $\ell_{1}$, $\ell_{2}$ and $\ell_{3}$ be three lines in $\mathbb{R}^{3}$,
passing through the origin, with $\alpha$ and $\pi-\alpha$ being the angles
between $\ell_{2}$ and $\ell_{3}$, $\beta$ and $\pi-\beta$ being the angles
between $\ell_{3}$ and $\ell_{1}$, and $\gamma$ and $\pi-\gamma$ being the
angles between $\ell_{1}$ and $\ell_{2}$. Because of the constraints on
$\alpha$, $\beta$ and $\gamma$, such lines exist. Each line $\ell_{j}$
intersects the unit sphere in two antipodal points, $q_{j}$ and
$q^{\prime}_{j}$. The three lines taken pairwise determine three planes
through the origin which then intersect the unit sphere in three great circles
$\mathscr{C}_{1}$, $\mathscr{C}_{2}$, $\mathscr{C}_{3}$, yielding the
preliminary setup described in Section 1.

Figure 2: The solid geometry problem

Next consider any three distinct points $A$, $B$ and $C$, with $A$ on
$\ell_{1}$, $B$ on $\ell_{2}$, and $C$ on $\ell_{3}$. Consider the triangle
$\triangle ABC$. See Figure 2. Now ask the following.

Question 2. Can $A$, $B$ and $C$ be selected so that the interior angle of
$\triangle ABC$ at $A$ is $\angle A$, the interior angle at $B$ is $\angle B$,
and the angle at $C$ is $\angle C$?

This leads to a claim somewhat similar to that in Section 1, and also a
connection between these two claims.

######  Proposition 2.

If $\angle A$, $\angle B$ and $\angle C$ do not exceed $\pi/2$, then Question
2 is answered in the affirmative.

######  Proposition 3.

Questions 1 and 2 are equivalent in that both depend only on the numbers
$\angle A$, $\angle B$, $\angle C$, $\alpha$, $\beta$, and $\gamma$, and the
answers to these questions are the same. Thus, Propositions 1 and 2 are
equivalent too.

###### Proof of Prop. 3.

Concerning the setup in this section, the sideline $\overleftrightarrow{BC}$
of $\triangle ABC$, when parallel translated so as to pass through the origin,
yields a line $\mathscr{L}_{1}$ that intersects the unit sphere in two
antipodal points $p_{1}$ and $p^{\prime}_{1}$. These points are concyclic with
$q_{2}$, $q_{3}$, $q^{\prime}_{2}$ and $q^{\prime}_{3}$, with their common
circle in the plane containing the lines $\mathscr{L}_{1}$, $\ell_{2}$,
$\ell_{3}$. Likewise, $\overleftrightarrow{CA}$ ($\overleftrightarrow{AB}$)
yields a line $\mathscr{L}_{2}$ ($\mathscr{L}_{3}$) and antipodal points
$p_{2}$ and $p^{\prime}_{2}$ ($p_{3}$ and $p^{\prime}_{3}$).

The six points $p_{1}$, $p^{\prime}_{1}$, $p_{2}$, $p^{\prime}_{2}$, $p_{3}$
and $p^{\prime}_{3}$ lie on a great circle of the unit sphere that is also in
a plane parallel to the plane containing the triangle $\Delta ABC$. We may
assume that going around this circle, the points occur in the cyclic order
$p_{1},p_{2},p_{3},p^{\prime}_{1},p^{\prime}_{2},p^{\prime}_{3}$, as before.
It is immediately seen that the distance along the arc connecting $p_{1}$ and
$p_{2}$ equals the interior angle of $\triangle ABC$ at $C$, and so forth.
Thus we achieve the complete setup in Section 1, manifesting the claimed
connection between the two questions.

∎

##  3 Extending Sullivan’s Construction

Before proving Proposition 2, a framework for exploring Question 2 will now be
developed, without yet assuming that $\angle A$, $\angle B$ and $\angle C$ are
bounded above by $\pi/2$. Without loss of generality, assume that $\ell_{1}$
is the $x$-axis, that $\ell_{2}$ is also in the $xy$-plane, but $\ell_{3}$ is
not in the $xy$-plane. Further assume that rotating the positive $x$-axis
counterclockwise by the angle $\gamma$ results in a ray along the line
$\ell_{2}$. Now, choose a positive number $a$, and let $b=a\csc\angle
A\sin\angle B$ and $c=a\csc\angle A\sin\angle C$.

Figure 3: Sullivan’s Construction

Let $B_{0}$ be the point along this ray whose coordinates are
$(c\cos\gamma,c\sin\gamma,0)$. Let $C_{0}$ be the point whose coordinates are
$(b\cos(\angle A+\gamma),b\sin(\angle A+\gamma),0)$. Let $A_{0}=O$ (the
origin). A direct check shows that $\angle C_{0}A_{0}B_{0}=\angle A$ , $\angle
A_{0}B_{0}C_{0}=\angle B$ , $\angle B_{0}C_{0}A_{0}=\angle C$ , dist($B_{0}$,
$C_{0}$) = $a$ , dist($C_{0}$, $A_{0}$) = $b$ and dist($A_{0}$, $B_{0}$) =
$c$. Now, rotate $B_{0}$ and $C_{0}$ about the origin by an arbitrary signed
angle $\theta$ to get points $B_{1}$ and $C_{1}$. Let $A_{1}=A_{0}=O$. Next,
translate $A_{1}$, $B_{1}$ and $C_{1}$ along the $x$ direction by an amount
$c\csc\gamma\sin\theta$ to get the points $A$, $B$ and $C^{\prime}$. Notice
that $\angle C^{\prime}AB=\angle A$ , $\angle ABC^{\prime}=\angle B$ , $\angle
BC^{\prime}A=\angle C$ , dist($B$, $C^{\prime}$) = $a$ , dist($C^{\prime}$,
$A$) = $b$ , dist($A$, $B$) = $c$. Also notice that $A$ is on $\ell_{1}$, $B$
is on $\ell_{2}$, but $C^{\prime}$ is not on $\ell_{3}$, since it is in the
$xy$-plane. See Figure 3.

The construction thus far is discussed in [Wetzel, 2010], where it is credited
to John M. Sullivan. By varying $\theta$, we will regard that $A$, $B$ and
$C^{\prime}$ are “moving points.” As $A$ is allowed to slide back and forth
along $\ell_{1}$ (crossing $O$), and $B$ does likewise along $\ell_{2}$,
keeping a distance $c$ from $A$, these two points move in a manner reminiscent
of the Trammel of Archimedes, a skewed version of it actually (cf. [Wetzel,
2010]). This mathematical model will now be extended to obtain a three-
dimension method for producing the desired triangle to fit the three given
lines.

Let $F$ be the projection of $C^{\prime}$ onto the line
$\overleftrightarrow{AB}$, and let $C^{\prime\prime}$ be the reflection of
$C^{\prime}$ about the line $\overleftrightarrow{AB}$. Now, consider rotating
$C^{\prime}$ in three dimensions, about the line $\overleftrightarrow{AB}$ by
a signed angle $\psi$ to obtain a point $\wideparen{C}$. When $\psi=0$,
$\wideparen{C}=C^{\prime}$, of course, but when $\psi=\pi$,
$\wideparen{C}=C^{\prime\prime}$. Moreover, for arbitrary $\psi$, the
orthogonal projection of $\wideparen{C}$ onto the $xy$-plane is on the line
segment $\overline{C^{\prime}C^{\prime\prime}}$. Notice too that the triangles
$\Delta A_{0}B_{0}C_{0}$, $\Delta A_{1}B_{1}C_{1}$, $\Delta ABC^{\prime}$,
$\Delta ABC^{\prime\prime}$ and $\Delta AB\wideparen{C}$ are all conguent.
Also, by varying both $\theta$ and $\psi$, we produce all possible triangles
$\Delta AB\wideparen{C}$ that are congruent to $\Delta A_{0}B_{0}C_{0}$, and
for which $A$ is on $\ell_{1}$ and $B$ is on $\ell_{2}$.

Figure 4: 3D Extension Analysis (in 2D)

Now, with $A$ and $B$ fixed at the moment, and with neither being $O$,
consider the circle $OAB$, as in Figure 4. At each point $P$ on this circle,
other than $A$ or $B$, the angle $\angle APB$ equals either $\gamma$ or
$\pi-\gamma$ (by the Inscribed Angle Theorem). If we now slide $A$ and $B$, by
continuously changing $\theta$, the same rigid motion that moves the segment
$\overline{AB}$ will also move the circle in such a way that the resulting
circle will still pass through all three of the points $O$, $A$ and $B$, even
though $O$ is stationary. The formula for this rigid motion is
$(x,y)\mapsto(x\cos\theta-y\sin\theta+c\csc\gamma\sin\theta\,,\,x\sin\theta+y\cos\theta)$.
Moreover, the line segment $\overline{C^{\prime}C^{\prime\prime}}$ also moves
according to this same rigid transformation.

Though they will not be needed in the rest of this paper, here are the
coordinates of the points discussed thus far:

$\begin{array}[]{ccl}B_{0}&:&(\,c\cos\gamma,\;c\sin\gamma,\;0\,)\\\
C_{0}&:&(\,b\cos(\angle A+\gamma),\;b\sin(\angle A+\gamma),\;0\,)\\\
B_{1}&:&(\,c\cos(\gamma+\theta),\;c\sin(\gamma+\theta),\;0\,)\\\
C_{1}&:&(\,b\cos(\angle A+\gamma+\theta),\;c\sin(\angle
A+\gamma+\theta),\;0\,)\\\ A&:&(\,c\csc\gamma\sin\theta,\;0,\;0\,)\\\
B&:&(\,c\cos(\gamma+\theta)+c\csc\gamma\sin\theta,\;c\sin(\gamma+\theta),\;0\,)\\\
C^{\prime}&:&(\,b\cos(\angle
A+\gamma+\theta)+c\csc\gamma\sin\theta,\;b\sin(\angle
A+\gamma+\theta),\;0\,)\\\ C^{\prime\prime}&:&(\,b\cos(-\angle
A+\gamma+\theta)+c\csc\gamma\sin\theta,\;b\sin(-\angle
A+\gamma+\theta),\;0)\\\ \wideparen{C}&\;:&(\,b\cos\angle
A\cos(\gamma+\theta)+c\csc\gamma\sin\theta-b\sin\angle
A\sin(\gamma+\theta)\cos\psi,\\\ &&(\,b\cos\angle
A\sin(\gamma+\theta)+b\sin\angle A\cos(\gamma+\theta)\cos\psi,\;b\sin
A\sin\psi\,)\\\ F&\;:&(b\cos\angle
A\cos(\gamma+\theta)+c\csc\gamma\sin\theta,\;b\cos\angle
A\sin(\gamma+\theta),\;0\,).\\\ \end{array}$

These coordinates could be useful in better understanding the framework, and
perhaps in implementing demonstrations of it. Also, the circle containing $O$,
$A$ and $B$ has the equation
$x^{2}+y^{2}=c\csc\gamma\,(\sin\theta\,x+\cos\theta\,y)$. A couple lemmas will
be helpful, primarily in proving Proposition 2, which is concerned with the
existence of a certain acute or right $\Delta ABC$, but these lemmas also
provide insight into the obtuse $\Delta ABC$ case.

######  Lemma 4.

The following are equivalent:

  * (i)

There exist values for $\theta$ and $\psi$ such that $\wideparen{C}$ lies on
the $z$-axis;

  * (ii)

The line segment $\overline{C^{\prime}C^{\prime\prime}}$ intersects the circle
$OAB$ (for any value of $\theta$).

The following are also equivalent:

  * (iii)

$F$ is on or inside the circle $OAB$, and $\angle
C\leq\max\\{\gamma,\pi-\gamma\\}$;

  * (iv)

$F$ is on or inside the circle $OAB$, and $\cos\gamma\leq\cos\angle C$ or
$\cos\gamma\geq-\cos\angle C$.

Moreover, (iii) implies (ii).

###### Proof.

As $\theta$ is continuously increased (or decreased), the circle $OAB$ and the
line segments $\overline{AB}$ and $\overline{C^{\prime}C^{\prime\prime}}$ will
all undergo the same continuous rigid motion. Suppose for a moment that
$\overline{C^{\prime}C^{\prime\prime}}$ intersects the circle at a point $G$.
As the circle and line segments move, the point $G$ moves with them, and
follows an elliptic path (by a theorem of Schooten; see [Wetzel, 2010]) in the
$xy$-plane. It must also remain concyclic with $O$, $A$ and $B$.

Consider now a reference frame (rigidly moving coordinate system) in which
$A$, $B$, $C^{\prime}$, $C^{\prime\prime}$, $F$ and $G$ are stationary. Here
$O$ becomes a moving point (no longer regarded as the origin), and moves
around the circle $ABG$.222It moves twice around this circle each time the
objects go around once in the original 3-space frame. Clearly, $O$ passes
through $A$, and passes through $B$, and these events alternate (strictly).
Thus it is clear that $O$ passes through $G$ as well. That is, there exists a
value for $\theta$ that makes $G=O$. Since $G$ lies on the line segment
$\overline{C^{\prime}C^{\prime\prime}}$, it is the orthogonal projection of
some $\wideparen{C}$ onto the $xy$-plane. Since $G=O$, this $\wideparen{C}$ is
on the $z$-axis of the original reference frame. Therefore, (ii) implies (i).
(The inverse of the rigid motion discussed earlier is
$(x,y)\mapsto(\;(x-c\csc\gamma\sin\theta)\cos\theta+y\sin\theta+c\csc\gamma\sin\theta\,,\,-(x-c\csc\gamma\sin\theta)\sin\theta+y\cos\theta\;)$,
which can be used to describe the path now followed by the moving point $O$,
by setting $x=y=0$.)

Conversely, assuming (i), the orthogonal projection of this $\wideparen{C}$
onto the $xy$-plane is $O$. Thus, $O$ must lie on
$\overline{C^{\prime}C^{\prime\prime}}$, and obviously it lies on the circle
$OAB$, and hence $\overline{C^{\prime}C^{\prime\prime}}$ and the circle $OAB$
intersect. Since these objects move together as $\theta$ varies, they will
still intersect, for any value of $\theta$. Thus, (i) implies (ii). The fact
that (iii) implies (ii) follows after observing that the circle $OAB$ consists
of the points $P$ for which $\angle APB$ is either $\gamma$ or $\pi-\gamma$,
so either $C^{\prime}$ or $C^{\prime\prime}$ is outside the circle. The
equivalence of (iii) and (iv) is straightforward to check.

∎

######  Lemma 5.

If condition $(ii)$ in Lemma 4 holds, then points $A$, $B$ and $C$, as
described in Proposition 2, exist.

###### Proof.

If $\ell_{3}$ is the $z$-axis, then the claim here follows immediately from
Lemma 4, by simply choosing $C$ to be the $\wideparen{C}$ on the $z$-axis.
Now, assume that $\ell_{3}$ is not the $z$-axis. Express the line $\ell_{3}$
parametrically as $x=mz$ and $y=nz$, for constants $m$ and $n$, not both zero.
Again, for some $\theta$ and some $\psi$, the corresponding $\wideparen{C}$ is
along the $z$-axis. Keeping this $\theta$ fixed, vary $\psi$ to get a vertical
circle (i.e. orthogonal to the $xy$-plane) of points $\wideparen{C}$. The line
$\ell_{3}$ either intersects this circle (if it is in the same plane as the
circle), or passes through the circle. In the former case, we will have again
found a suitable choice for $C$.

Now assume the latter case. If we now change $\theta$, the vertical circle of
possible $\wideparen{C}$ can be made to lie in a vertical plane that is
parallel or equal to the vertical plane containing $\ell_{3}$. To see this,
consider the orthogonal projections onto the $xy$-plane. The circle of
possible $\wideparen{C}$ projects onto the segment
$\overline{C^{\prime}C^{\prime\prime}}$. The line $\ell_{3}$ projects onto a
line $\ell$ in the $xy$-plane, given by the equation $nx=my$. The segment
$\overline{C^{\prime}C^{\prime\prime}}$ makes a complete rotation as $\theta$
varies, and so it can be made either to lie on $\ell$ or to be parallel to
$\ell$. In the former case, we would again have $\ell_{3}$ intersecting the
circle of possible $\wideparen{C}$, and so again a suitable point $C$ would be
obtained.

Now assume the latter case. For this value of $\theta$, the line $\ell_{3}$
does not pass through the vertical circle. But for the value of $\theta$
considered earlier, $\ell_{3}$ did pass through the circle. By continuity,
there must be a value of $\theta$ for which $\ell_{3}$ intersects the circle,
once again giving us a point $\wideparen{C}$ that will serve as a suitable
choice for $C$.

∎

We are now prepared to prove Proposition 2, which together with Proposition 3,
also will establish Proposition 1.

###### Proof of Prop. 2.

Notice that $\angle A\leq\pi/2$ and $\angle B\leq\pi/2$ ensure that the
segments $\overline{AB}$ and $\overline{C^{\prime}C^{\prime\prime}}$
intersect, at $F$. Since $\overline{AB}$ is a chord of the circle $OAB$, $F$
is in the interior of the circle, unless $F=A$ or $F=B$. Since $\angle
C\leq\pi/2$, it follows that either $\angle C\leq\gamma$ or $\angle
C\leq\pi-\gamma$. The proposition then follows quickly from the two lemmas.

∎

##  4 Afterthoughts

Suppose that points $A$, $B$ and $C$ are selected points on $\ell_{1}$,
$\ell_{2}$ and $\ell_{3}$, respectively, as in Section 2. If the three lines
happen to be orthogonal to each other, then it is easily seen that the
triangle $\Delta ABC$ cannot be obtuse, and must instead be an acute or a
right triangle. Proposition 2 ensures that any acute or right triangle is
possible here. Another immediate consequence of Proposition 2 is as follows.

######  Corollary 6.

A tetrahedron with three prescribed edge lines at one of its vertices can have
an opposite face that is congruent to any given acute or right triangle.

Extensive experiments using Mathematica and C++ seem to indicate how to extend
Proposition 2 to the obtuse triangle case, where one of the numbers $\angle
A$, $\angle B$, $\angle C$ exceeds $\pi/2$. Also, a practical variation of
Question 2 is obtained by replacing the three lines, $\ell_{1}$, $\ell_{2}$
and $\ell_{3}$, with three rays from the origin. This revised question is
closely coupled with the “Three-Point Perspective (Pose) Problem” discussed in
[Haralick et al., 1994] and [Rieck-Wang, 2021]. Not surprisingly, in this
variation of Question 2, the acute triangle case and the obtuse triangle case
again yield quite different results. Thorough testing has resulted in several
proven claims and a number of conjectures. The “discriminant of Grunert’s
system” and the “basic toroids” considered in [Rieck-Wang, 2021] play crucial
roles in the analysis.

Finally, Question 1 and Proposition 1 can be recast in terms or the real
projective plane $\mathbb{RP}^{2}$. This is commonly modeled by taking its
“points” to actually be pairs of antipodal points on the real unit sphere.
Another useful model identifies the points of the projective plane with the
lines through the origin in $\mathbb{R}^{3}$. The correspondence between these
two models is evident since each line through the origin intersects the sphere
in a pair of antipodal points.

The “elliptic plane” is a name often given to the manifold that results from
equipping $\mathbb{RP}^{2}$ with the metric inherited from the unit sphere.
(The name comes from “elliptic geometry,” which confusingly has little to do
with ellipses.) We will regard that $\mathbb{RP}^{2}$ is equipped with this
metric. Using the reasoning here, the following claim can be quickly seen to
be a consequence of Proposition 1.

######  Corollary 7.

Let $P_{1}$, $P_{2}$ and $P_{3}$ be three collinear points on the elliptic
plane such that $\hbox{dist}(P_{2},P_{3})\leq\pi/2$,
$\hbox{dist}(P_{3},P_{1})\leq\pi/2$, $\hbox{dist}(P_{1},P_{2})\leq\pi/2$, and
$\hbox{dist}(P_{2},P_{3})+\hbox{dist}(P_{3},P_{1})+\hbox{dist}(P_{1},P_{2})=\pi$.
Also, let $\alpha$, $\beta$ and $\gamma$ be any strictly positive numbers with
$\alpha+\beta+\gamma<2\pi$, $\alpha<\beta+\gamma$, $\beta<\gamma+\alpha$ and
$\gamma<\alpha+\beta$. Then, there exist points $Q_{1}$, $Q_{2}$ and $Q_{3}$
with $P_{1},Q_{2},Q_{3}$ collinear, $P_{2},Q_{3},Q_{1}$, collinear,
$P_{3},Q_{1},Q_{2}$ collinear,
$\hbox{dist}(Q_{2},Q_{3})=\min\\{\alpha,\pi-\alpha\\}$,
$\hbox{dist}(Q_{3},Q_{1})=\min\\{\beta,\pi-\beta\\}$, and
$\hbox{dist}(Q_{1},Q_{2})=\min\\{\gamma,\pi-\gamma\\}$.

This basically means that whenever three collinear points $P_{1}$, $P_{2}$ and
$P_{3}$ in $\mathbb{RP}^{2}$ are not “bunched too close together,” it is
always possible to construct a triangle in $\mathbb{RP}^{2}$ (the projection
of a spherical triangle onto $\mathbb{RP}^{2}$), of any possible shape, such
that each of its sidelines is incident, in any prescribed order, with one of
the three collinear points.

## References

  * [Haralick et al., 1994] Haralick, R. M., Lee, C.-N., Ottenberg, K., and Nölle, N.  Review and Analysis of Solutions of the Three Point Perspective Pose Estimation Problem.  J. Computer Vision, 13(3): 331–356.
  * [Rieck-Wang, 2021] Rieck, M. Q., and Wang, B.  Locating Perspective Three-Point Problem Solutions in Spatial Regions.  J. Mathematical Imaging and Vision, 63(8): 953–973.
  * [Wetzel, 2010] Wetzel, J. E.  An Ancient Elliptic Locus.  Amer. Math. Monthly, 117(2): 161–167.