# Finding Spanning Trees with Perfect Matchings

Kristóf Bérczi Eötvös Loránd University, Hungary<EMAIL_ADDRESS> Tamás Király Eötvös Loránd University, Hungary<EMAIL_ADDRESS> Yusuke Kobayashi Kyoto University, Japan. Email:
<EMAIL_ADDRESS> Yutaro Yamaguchi Osaka University, Japan.
Email<EMAIL_ADDRESS> Yu Yokoi Tokyo Institute of
Technology, Japan. Email<EMAIL_ADDRESS>
###### Abstract

We investigate the tractability of a simple fusion of two fundamental
structures on graphs, a spanning tree and a perfect matching. Specifically, we
consider the following problem: given an edge-weighted graph, find a minimum-
weight spanning tree among those containing a perfect matching. On the
positive side, we design a simple greedy algorithm for the case when the graph
is complete (or complete bipartite) and the edge weights take at most two
values. On the negative side, the problem is NP-hard even when the graph is
complete (or complete bipartite) and the edge weights take at most three
values, or when the graph is cubic, planar, and bipartite and the edge weights
take at most two values.

We also consider an interesting variant. We call a tree strongly balanced if
on one side of the bipartition of the vertex set with respect to the tree, all
but one of the vertices have degree $2$ and the remaining one is a leaf. This
property is a sufficient condition for a tree to have a perfect matching,
which enjoys an additional property. When the underlying graph is bipartite,
strongly balanced spanning trees can be written as matroid intersection, and
this fact was recently utilized to design an approximation algorithm for some
kind of connectivity augmentation problem. The natural question is its
tractability in nonbipartite graphs. As a negative answer, it turns out NP-
hard to test whether a given graph has a strongly balanced spanning tree or
not even when the graph is subcubic and planar.

#### Keywords:

Algorithm, NP-hardness, Spanning tree, Perfect matching

##  1 Introduction

Spanning trees and perfect matchings are two of the most fundamental tractable
structures in combinatorial optimization on graphs. It is well-known that a
minimum-weight spanning tree or perfect matching in an edge-weighted graph can
be found in polynomial time [20, 28, 5, 7]. These problems are foundational
for the development of not only graph algorithms but also the theory of
combinatorial optimization on more abstract targets such as matroids and
discrete convex functions (cf. [10, 26, 12, 29]).

In this paper, we investigate a kind of fusion of these two structures. The
simplest setting is to determine whether a given graph has a spanning tree
containing a perfect matching or not. This problem is easy, because a trivial
necessary condition that the graph is connected and has a perfect matching is
also sufficient (Observation 3.1).

The natural question is as follows: what about finding a minimum-weight such
spanning tree in an edge-weighted graph? We give a solid answer to this
question (Theorem 2.2). On the positive side, this optimization problem is
tractable in the very restricted situation when the graph is a complete or
complete bipartite graph and the edge weights are restricted to at most two
values. On the negative side, the problem is NP-hard even if the graph is a
complete or complete bipartite graph and the edge weights are restricted to at
most three values (say, $0$, $1$, or $2$), or if the graph is cubic, planar,
and bipartite and the edge weights are restricted to at most two values (say,
$0$ or $1$).

We also consider a variant of a spanning tree with a perfect matching. A
trivial necessary condition for a tree to have a perfect matching is that the
bipartition of the vertex set is balanced; that is, if we color the vertices
with two colors so that any two adjacent vertices are colored differently,
then the number of vertices colored with each of the two colors is the same.
This is clearly not sufficient, but it can be strengthened to become
sufficient as follows.

We say that a tree is _strongly balanced_ if on one side of the bipartition,
exactly one vertex is a leaf (that is of degree $1$) and all the other
vertices are of degree $2$. Norose and Yamaguchi [27] showed that a tree is
strongly balanced if and only if it has a perfect matching and, for some leaf,
a path from the leaf to any vertex in the tree is an alternating path with
respect to the perfect matching. This property was utilized to design a
nontrivial approximation algorithm for a kind of connectivity augmentation
problem [27] and travelling salesman problem [11]. An important fact is that,
for a bipartite graph, strongly balanced spanning trees can be represented as
the common bases of two matroids (Observation 4.1), which enables us to find a
minimum-weight strongly balanced spanning tree in polynomial time with the aid
of weighted matroid intersection algorihtms [21, 22, 9, 19, 2]. Also, as
pointed out in [27], it is interesting that this problem in fact commonly
generalizes two fundamental special cases of weighted matroid intersection:
finding a minimum-weight perfect matching in bipartite graphs and finding a
minimum-weight arborescence in directed graphs.

The natural question, again, is as follows: what about the tractability of
strongly balanced spanning trees in nonbipartite graphs? We give a negative
answer to this question (Theorem 2.3): it is NP-hard to test whether a given
graph has a strongly balanced spanning tree or not, even if the graph is
subcubic and planar.

Problems of finding a spanning tree with additional constraints have been
studied extensively, some of which were motivated by applications to
communication networks. For example, there are several studies on spanning
trees with degree bounds [4, 13, 14, 30] and spanning trees with small
diameter [17, 16, 31]. Our problems also align with this context. The
additional condition of containing a perfect matching implies that each node
can be paired with another to have mutual backup, expressing network
robustness in a sense. It is worth noting that the constraints of having
partners and backups were studied also in the dominating set problem [18, 3,
32]. Spanning trees with perfect matchings also appear in characterization of
chemical structures [35, 34], and counting them in special graphs has recently
been paid attention [24].

The rest of the paper is organized as follows. In Section 2, we describe
necessary definitions, and formally state the problems and our results. In
Section 3, we give a simple, polynomial-time algorithm for finding a minimum-
weight spanning tree containing a perfect matching for the restricted inputs,
and show the NP-hardness of the problem by a reduction from the Hamiltonian
cycle problem. In Section 4, we prove the NP-hardness of finding a strongly
balanced spanning tree by a reduction from the planar 3-SAT problem. In
Section 5, we conclude the paper with possible future work.

##  2 Preliminaries

###  2.1 Definitions

Let $G=(V,E)$ be a graph, which we assume to be simple and undirected unless
otherwise specified. We refer the readers to [29] for basic concepts and
notation on graphs.

An edge set $M\subseteq E$ is a _matching_ in $G$ if the edges in $M$ do not
share their end vertices. For a fixed matching, a vertex is said to be
_covered_ (or _matched_) if it is an end vertex of an edge in the matching,
and _exposed_ otherwise. A matching is _perfect_ if all the vertices are
covered. Let $\mathrm{def}(G)$ denote the _deficiency_ of $G$, which is
defined as the minimum number of vertices exposed by a matching in $G$; in
other words, it is the number of vertices minus twice the maximum cardinality
of a matching.

A graph is said to be _bipartite_ if its vertex set admits a _bipartition_
$(V^{+},V^{-})$ such that every edge has one of its end vertices in $V^{+}$
and the other in $V^{-}$; possibly $V^{+}=\emptyset$ or $V^{-}=\emptyset$. We
say that a bipartite graph (with a fixed bipartition) is _balanced_ if
$|V^{+}|=|V^{-}|$. Note that if a bipartite graph has a perfect matching, then
it is balanced (regardless of the bipartition).

Let $T$ be a spanning tree of $G$. A tree is bipartite, and let
$(V_{T}^{+},V_{T}^{-})$ denote a bipartition of $V$ with respect to $T$, i.e.,
$V_{T}^{+}\cup V_{T}^{-}=V$, $V_{T}^{+}\cap V_{T}^{-}=\emptyset$, and every
edge in $T$ connects a vertex in $V_{T}^{+}$ and one in $V_{T}^{-}$. Such a
bipartition is unique up to the symmetry of $V_{T}^{+}$ and $V_{T}^{-}$. Note
that if $T$ has a perfect matching, then it is unique and $T$ is balanced. We
say that $T$ is _strongly balanced_ if on one side of the bipartition, say
$V_{T}^{+}$ by symmetry, exactly one vertex is a leaf (that is of degree $1$)
and all the other vertices are of degree $2$. Observe that if $T$ is strongly
balanced, then $T$ is balanced. As a relation with a perfect matching, the
following characterization is known.

######  Lemma 2.1 (Norose and Yamaguchi [27]).

For a tree $T$, the following two statements are equivalent.

  * •

$T$ is strongly balanced.

  * •

$T$ has a perfect matching $M$, and there exists a leaf $r$ such that a path
in $T$ from $r$ to any vertex alternates between the edges in $M$ and in
$E\setminus M$.

Suppose that $G$ is associated with edge weight $w\colon E\to\mathbb{R}$. We
define the _weight_ of each edge set $F\subseteq E$ as $w(F)\coloneq\sum_{e\in
F}w(e)$.

###  2.2 Problems and Our Results

We are now ready to state the problems. In the following sections, those
problems are referred to as their abbreviated names.

######  Problem (Perfectly Matchable Spanning Tree (PMST)).

Input:

A graph $G=(V,E)$.

Goal:

Decide whether $G$ has a spanning tree containing a perfect matching or not.

######  Problem (Minimum Perfectly Matchable Spanning Tree (MinPMST)).

Input:

A graph $G=(V,E)$ with edge weight $w\colon E\to\mathbb{R}$.

Goal:

Minimize $w(T)$ subject to $T$ is a spanning tree of $G$ containing a perfect
matching.

######  Problem (Strongly Balanced Spanning Tree (SBST)).

Input:

A graph $G=(V,E)$.

Goal:

Decide whether $G$ has a strongly balanced spanning tree $T$ or not.

######  Problem (Minimum Strongly Balanced Spanning Tree (MinSBST)).

Input:

A graph $G=(V,E)$ with edge weight $w\colon E\to\mathbb{R}$.

Goal:

Minimize $w(T)$ subject to $T$ is a strongly balanced spanning tree of $G$.

The main results shown in this paper are summarized as follows.

######  Theorem 2.2.

  1. 1.

MinPMST can be solved in polynomial time if $G$ is a complete or complete
bipartite graph and $|\mathrm{cod}(w)|\leq 2$, where
$\mathrm{cod}(w)\coloneq\\{\,w(e)\mid e\in E\,\\}$ denotes the codomain of
$w$.

  2. 2.

MinPMST is NP-hard even if the input is restricted as follows:

    1. (a)

$G$ is a cubic planar bipartite graph and $|\mathrm{cod}(w)|\leq 2$.

    2. (b)

$G$ is a complete or complete bipartite graph and $|\mathrm{cod}(w)|\leq 3$.

######  Theorem 2.3.

SBST is NP-hard even if $G$ is restricted to a subcubic planar graph.

##  3 On Perfectly Matchable Spanning Trees (Proof of Theorem 2.2)

In this section, we prove Theorem 2.2. We start with an easy observation,
which immediately leads to the tractability of PMST with the aid of
polynomial-time algorithms for finding a maximum matching in graphs [8]; just
find a perfect matching, and make it connected by adding edges between
different connected components, one-by-one.

######  Observation 3.1.

A graph $G$ has a spanning tree containing a perfect matching if and only if
$G$ is connected and has a perfect matching.

In Section 3.1, we prove Statement 1 by giving a solution to MinPMST when the
graph is a complete or complete bipartite graph and there are at most two
weight values. In Section 3.2, we prove Statement 2 by giving a reduction from
the Hamiltonian cycle problem with an input restriction to MinPMST with the
stated input restrictions.

###  3.1 Tractable Case (Statement 1)

Since all the spanning trees of a fixed graph have the same number of edges,
the case when $|\mathrm{cod}(w)|=1$ reduces to PMST. Suppose that
$|\mathrm{cod}(w)|=2$. Then, the objective is rephrased as minimizing the
number of heavier edges. Thus, without loss of generality, we assume that
$\mathrm{cod}(w)=\\{0,1\\}$.

Let us focus on the complete graph case (the complete bipartite graph case is
almost the same; see Remark 3.3 at the end of this section). Let $G=(V,E)$ be
a complete graph with edge weight $w\colon E\to\\{0,1\\}$, where we assume
$|V|$ is even (otherwise, $G$ has no perfect matching). Let $G_{0}=(V,E_{0})$
be the subgraph consisting of all the edges of weight $0$, i.e.,
$E_{0}=\\{\,e\in E\mid w(e)=0\,\\}$. Then, by Observation 3.1, the following
augmentation problem with input $H=G_{0}$ is equivalent to MinPMST with the
current restriction.

######  Problem (Augmentation on PMST (AugPMST)).

Input:

A graph $H$.

Goal:

Minimize the number of additional edges to make $H$ connected and perfectly
matchable.

For AugPMST, we show a complete characterization as follows, which leads to a
solution to the original problem MinPMST when $G$ is a complete graph and
$|\mathrm{cod}(w)|=2$. For a graph $H$, we denote by $\mathrm{opt}(H)$ the
optimal value for the input $H$ of AugPMST. Also, let $c(H)$ denote the number
of connected components of $H$, and $c_{0}(H)$ and $c_{+}(H)$ denote the
numbers of connected components $K$ with $\mathrm{def}(K)=0$ and with
$\mathrm{def}(K)>0$, respectively.

######  Lemma 3.2.

  1. 1.

If $\mathrm{def}(H)=0$, then $\mathrm{opt}(H)=c(H)-1$.

  2. 2.

Suppose that $\mathrm{def}(H)>0$.

    1. (a)

If $\frac{1}{2}\mathrm{def}(H)<c_{+}(H)$, then $\mathrm{opt}(H)=c(H)-1$.

    2. (b)

If $\frac{1}{2}\mathrm{def}(H)\geq c_{+}(H)$, then
$\mathrm{opt}(H)=\frac{1}{2}\mathrm{def}(H)+c_{0}(H)$.

###### Proof.

We show this lemma by induction on the number of edges in $H$ (in descending
order). The proof is based on case analysis with respect to
$\varphi(H)\coloneq\left(\frac{1}{2}\mathrm{def}(H),c_{+}(H),c_{0}(H)\right)$.

We first observe all the possible changes of $\varphi(H)$ by adding an edge to
$H$. Suppose that $\varphi(H)=(i,j,k)$. Let $H^{\prime\prime}$ be any graph
obtained from $H$ by adding an edge. Then, there are four possible cases as
follows.

  * •

Suppose that we add an edge between two vertices in the same connected
component of $H$ such that every maximum matching covers at least one of the
two vertices. Then, $\varphi(H^{\prime\prime})=(i,j,k)$.

  * •

Suppose that we add an edge between two vertices in the same connected
component $K$ of $H$ such that some maximum matching exposes both of the two
vertices. Then, $\varphi(H^{\prime\prime})=(i-1,j,k)$ or $(i-1,j-1,k+1)$ (when
$\mathrm{def}(K)>2$ or $\mathrm{def}(K)=2$, respectively).

  * •

Suppose that we add an edge between two vertices in different connected
components $K_{1},K_{2}$ of $H$ such that every maximum matching covers at
least one of the two vertices. Then, $\varphi(H^{\prime\prime})=(i,j-1,k)$ or
$(i,j,k-1)$ (when $\min(\mathrm{def}(K_{1}),\mathrm{def}(K_{2}))>0$ or
$\min(\mathrm{def}(K_{1}),\mathrm{def}(K_{2}))=0$, respectively).

  * •

Suppose that we add an edge between two vertices in different connected
components $K_{1},K_{2}$ of $H$ such that some maximum matching exposes both
of the two vertices. Then, $\varphi(H^{\prime\prime})=(i-1,j-2,k+1)$ or
$(i-1,j-1,k)$ (when $\mathrm{def}(K_{1})=\mathrm{def}(K_{2})=1$ or
$\max(\mathrm{def}(K_{1}),\mathrm{def}(K_{2}))>1$, respectively).

We then prove the statement for each case.

(i) When $\varphi(H)=(0,0,k)$ $(k\geq 1)$ (including the base case that $H$ is
complete), we show $\mathrm{opt}(H)=k-1$ (Statement 1). In this case, $H$ has
a perfect matching as $\mathrm{def}(H)=0$, so it is clearly optimal (necessary
and sufficient) to make $H$ connected by adding $k-1$ edges.

(ii) When $\varphi(H)=(1,1,k)$ $(k\geq 0)$, we show $\mathrm{opt}(H)=k+1$
(Statement 2b). In this case, $H$ has a unique connected component $K$ with
$\mathrm{def}(K)>0$, which satisfies $\mathrm{def}(K)=2$.

Let $H^{\prime}$ be the graph obtained from $H$ by adding an edge between two
vertices such that some maximum matching exposes both of them, which are in
the same connected component $K$. Then, $\varphi(H^{\prime})=(0,0,k+1)$, and
$\mathrm{opt}(H^{\prime})=k$ more edges are sufficient by induction hypothesis
(Statement 1), and hence
$\mathrm{opt}(H)\leq\mathrm{opt}(\varphi(H^{\prime}))+1=k+1$.

Let $H^{\prime\prime}$ be any graph obtained from $H$ by adding an edge.
Following the observation at the beginning, we have
$\varphi(H^{\prime\prime})=(1,1,k)$, $(0,0,k+1)$, or $(1,1,k-1)$, in which we
have $\mathrm{opt}(H^{\prime\prime})=k+1$, $k$, or $k$, respectively, by
induction hypothesis (Statement 1 or 2b), and hence
$\mathrm{opt}(H)\geq\min_{H^{\prime\prime}}\mathrm{opt}(\varphi(H^{\prime\prime}))+1=k+1$.

(iii) When $\varphi(H)=(i,1,k)$ $(i\geq 2,\ k\geq 0)$, we show
$\mathrm{opt}(H)=k+i$ (Statement 2b). In this case, $H$ has a unique connected
component $K$ with $\mathrm{def}(K)>0$, which satisfies $\mathrm{def}(K)=2i$.
This case is almost the same as the previous one. We have
$\varphi(H^{\prime})=(i-1,1,k)$ and $\varphi(H^{\prime\prime})=(i,1,k)$,
$(i-1,1,k)$, or $(i,1,k-1)$. By induction hypothesis (Statement 2b), we obtain
$\mathrm{opt}(H)\leq k+i$ and $\mathrm{opt}(H)\geq k+i$ as with the previous
case.

(iv) When $\varphi(H)=(i,2i,k)$ $(i\geq 1,\ k\geq 0)$, we show
$\mathrm{opt}(H)=k+2i-1$ (Statement 2a). In this case, $H$ has $2i$ connected
components, each of which has deficiency exactly $1$.

Let $H^{\prime}$ be the graph obtained from $H$ by adding an edge between two
vertices such that some maximum matching exposes both of them, which are in
different connected components $K_{1},K_{2}$ with
$\mathrm{def}(K_{1})=\mathrm{def}(K_{2})=1$. Then,
$\varphi(H^{\prime})=(i-1,2(i-1),k+1)$. By induction hypothesis (Statement 1
or 2a), $\mathrm{opt}(H^{\prime})=k+2i-2$ more edges are sufficient, and hence
$\mathrm{opt}(H)\leq k+2i-1$.

Let $H^{\prime\prime}$ be any graph obtained from $H$ by adding an edge.
Following the observation at the beginning, we have
$\varphi(H^{\prime\prime})=(i,2i,k)$, $(i,2i-1,k)$, $(i,2i,k-1)$, or
$(i-1,2(i-1),k+1)$, in which we have $\mathrm{opt}(H^{\prime\prime})=k+2i-1$
or $k+2i-2$ by induction hypothesis (Statement 1 or 2a), and hence
$\mathrm{opt}(H)\geq k+2i-1$.

(v) The remaining case is when $\varphi(H)=(i,j,k)$ $(i\geq 2,\ 1<j<2i,\ k\geq
0)$. In this case, $H$ has two different connected components $K_{1},K_{2}$
with $\mathrm{def}(K_{1})\geq 1$ and $\mathrm{def}(K_{2})\geq 2$. Note that
there are two possible cases: $i<j$ (Statement 2a) and $i\geq j$ (Statement
2b).

Let $H^{\prime}$ be the graph obtained from $H$ by adding an edge between two
vertices such that some maximum matching exposes both of them, one of them is
in $K_{1}$, and the other is in $K_{2}$. Then, the resulting component of
$H^{\prime}$ still has a positive deficiency, and hence
$\varphi(H^{\prime})=(i-1,j-1,k)$. No matter in which case we are (i.e., $i<j$
or $i\geq j$), the relation between $i$ and $j$ is preserved and we have
$\frac{1}{2}\mathrm{def}(H^{\prime})=\frac{1}{2}\mathrm{def}(H)-1$,
$c(H^{\prime})=c(H)-1$, and $c_{0}(H^{\prime})=c_{0}(H)$. Thus, by induction
hypothesis (Statement 2a or 2b, respectively), the stated number of additional
edges in total is indeed sufficient.

Let $H^{\prime\prime}$ be any graph obtained from $H$ by adding an edge.
Following the observation at the beginning, we have
$\varphi(H^{\prime\prime})=(i,j,k)$, $(i-1,j,k)$, $(i-1,j-1,k+1)$,
$(i,j-1,k)$, $(i,j,k-1)$, $(i-1,j-2,k+1)$, or $(i-1,j-1,k)$. In any case, by
induction hypothesis, the stated number of additional edges is necessary as
follows, which completes the proof.

  * •

In any case, we have
$\frac{1}{2}\mathrm{def}(H^{\prime\prime})+c_{0}(H^{\prime\prime})\geq\frac{1}{2}\mathrm{def}(H)+c_{0}(H)-1$
and $c(H^{\prime\prime})\geq c(H)-1$. Thus, if $H$ and $H^{\prime\prime}$ are
in the same situation (which is applied, Statement 2a or 2b), then the
consequence is clear.

  * •

Suppose that Statement 2a is applied to $H$ and Statement 2b to
$H^{\prime\prime}$. In this case, we have $j=i+1$ and
$\varphi(H^{\prime\prime})=(i-1,j-2,k+1)$ or $(i,j-1,k)$. Then,
$\mathrm{opt}(H^{\prime\prime})=\frac{1}{2}\mathrm{def}(H^{\prime\prime})+c_{0}(H^{\prime\prime})=i+k=j+k-1=c(H)-1$,
which means that $c(H)\ (\geq c(H)-1)$ additional edges in total are necessary
in this case.

  * •

Suppose that Statement 2b is applied to $H$ and Statement 2a to
$H^{\prime\prime}$. In this case, we have $j=i$ and
$\varphi(H^{\prime\prime})=(i-1,j,k)$. Then,
$\mathrm{opt}(H^{\prime\prime})=c(H^{\prime\prime})-1=j+k-1=i+k-1=\frac{1}{2}\mathrm{def}(H)+c_{0}(H)-1$,
which means that $\frac{1}{2}\mathrm{def}(H)+c_{0}(H)$ additional edges in
total are necessary in this case. ∎

The proof (the definition of $H^{\prime}$ in each case) gives a simple greedy
algorithm for AugPMST as follows.

Step 0.

Set $\tilde{H}\leftarrow H$, and find a maximum matching $\tilde{M}$ in
$\tilde{H}$.

Step 1.

While there exist two different connected components $K_{1},K_{2}$ of
$\tilde{H}$ with $\mathrm{def}(K_{1})\geq 1$ and $\mathrm{def}(K_{2})\geq 2$
(in Case (v)), pick two vertices $v_{1},v_{2}$ exposed by $\tilde{M}$ such
that $v_{1}$ is in $K_{1}$ and $v_{2}$ is in $K_{2}$, and add an edge
$\\{v_{1},v_{2}\\}$ to $\tilde{H}$ and $\tilde{M}$.

Step 2.

While there exist two different connected components $K_{1},K_{2}$ of
$\tilde{H}$ with $\mathrm{def}(K_{1})=\mathrm{def}(K_{2})=1$ (in Case (iv)),
pick two vertices $v_{1},v_{2}$ exposed by $\tilde{M}$ such that $v_{1}$ is in
$K_{1}$ and $v_{2}$ is in $K_{2}$, and add an edge $\\{v_{1},v_{2}\\}$ to
$\tilde{H}$ and $\tilde{M}$.

Step 3.

While $\mathrm{def}(\tilde{H})>0$ (in Case (ii) or (iii)), pick two vertices
$v_{1},v_{2}$ exposed by $\tilde{M}$ (which are in the same connected
component of $\tilde{H}$ by Steps 1 and 2), and add an edge
$\\{v_{1},v_{2}\\}$ to $\tilde{H}$ and $\tilde{M}$.

Step 4.

While $\tilde{H}$ is not connected (in Case (i)), pick two vertices
$v_{1},v_{2}$ in different connected components of $\tilde{H}$, and add an
edge $\\{v_{1},v_{2}\\}$ to $\tilde{H}$.

The bottleneck of its computational time is usually finding a maximum matching
in $H$, and the other parts are simply implemented in linear time. Thus, it
runs in $\mathrm{O}(\min(\sqrt{n}m+n,n^{\omega}))$ time [25, 15, 33], where
$n$ and $m$ are the numbers of vertices and edges in $H$, respectively, and
$\omega<2.372$ is the matrix multiplication exponent [6]. For the original
problem MinPMST when $G$ is a complete graph and $|\mathrm{cod}(w)|=2$, if the
input is given by specifying which edges have the smaller weight, it runs in
$\mathrm{O}(\min(\sqrt{n}m_{0}+n,n^{\omega}))$ time, where $n$ is the number
of vertices and $m_{0}$ is the number of edges having the smaller weight.

######  Remark 3.3.

Lemma 3.2 holds as it is if the underlying graph (i.e., $H$ together with all
possible additional edges) is a balanced complete bipartite graph, where the
balancedness is necessary to admit a perfect matching. Also, the above greedy
algorithm (with appropriate choices of $v_{1}$ and $v_{2}$ as well as $K_{1}$
and $K_{2}$ in Steps 1–4) works for MinPMST when $G$ is a balanced complete
bipartite graph and $|\mathrm{cod}(w)|=2$.

###  3.2 NP-Hardness (Statement 2)

We refer to a cycle $C$ in a graph as a sequence of vertices
$(v_{1},v_{2},\dots,v_{\ell},v_{1})$, where the vertices
$v_{1},v_{2},\dots,v_{\ell}$ $(\ell\geq 3)$ are all distinct and in the graph
there exists an edge $\\{v_{i},v_{i+1}\\}$ for each $i=1,2,\dots,\ell-1$ as
well as an edge $\\{v_{\ell},v_{1}\\}$. A cycle is called _Hamiltonian_ if it
contains all the vertices in the graph. The following problem is one of the
most fundamental NP-complete problems, which is NP-complete even for cubic
planar bipartite graphs.

######  Problem (Hamiltonian Cycle (HC)).

Input:

A graph $G=(V,E)$.

Goal:

Test whether $G$ has a Hamiltonian cycle or not.

######  Theorem 3.4 (Akiyama, Nishizeki, and Saito [1]).

HC is NP-complete even if $G$ is restricted to a cubic planar bipartite graph.

We prove Statement 2 of Theorem 2.2 by reducing this restricted HC to MinPMST
with stated restrictions. Let $G=(V,E)$ be a cubic planar bipartite graph, and
fix its planar embedding. We construct from $G$ a cubic planar bipartite graph
$\tilde{G}=(\tilde{V},\tilde{E})$ with edge weight
$\tilde{w}\colon\tilde{E}\to\\{0,1\\}$ as follows (see Figure 1).

For each edge $e=\\{u,v\\}\in E$, replace $e$ with two disjoint paths of
length $3$ between $u$ and $v$; in each path, the only middle edge is of
weight $1$ and the other two edges are of weight $0$. For each vertex $u\in
V$, let $f_{u,1},f_{u,2},f_{u,3}\in E$ denote the three edges incident to $u$
in this order in the clockwise direction, and then let
$u^{\prime}_{1},u^{\prime}_{2},\dots,u^{\prime}_{6}$ be the new vertices
adjacent to $u$ in this order, where $u^{\prime}_{2i-1}$ and $u^{\prime}_{2i}$
are created instead of the edge $f_{u,i}$ for each $i=1,2,3$. Rename $u$ as
$\tilde{u}_{0}$, merge $u^{\prime}_{4}$ and $u^{\prime}_{5}$ into a single
vertex $\tilde{u}_{1}$, $u^{\prime}_{6}$ and $u^{\prime}_{1}$ into
$\tilde{u}_{2}$, and $u^{\prime}_{2}$ and $u^{\prime}_{3}$ into
$\tilde{u}_{3}$, and remove one of the two parallel edges of weight $0$
between $\tilde{u}_{0}$ and $\tilde{u}_{i}$ for each $i=1,2,3$.

Figure 1: Construction of $\tilde{G}$ from $G$. The middle graph is the
intermediate graph just after replacing each edge with two disjoint paths.
Dashed lines represent edges of weight $0$, and solid lines represent edges of
weight $1$. In this example, $\tilde{e}$ and $\tilde{e}^{\prime}$ are derived
from $e=f_{u,1}=f_{v,3}$.

The resulting graph $\tilde{G}=(\tilde{V},\tilde{E})$ is indeed a cubic planar
bipartite graph. The following claim completes the proof of Statement 2a.

######  Claim 3.5.

$G$ has a Hamiltonian cycle if and only if $\tilde{G}$ has a spanning tree
$\tilde{T}$ containing a perfect matching with $\tilde{w}(\tilde{T})\leq|V|$.

###### Proof.

Suppose that $G$ has a Hamiltonian cycle $X$. By Observation 3.1, it suffices
to construct a connected subgraph
$\tilde{G}^{\prime}=(\tilde{V},\tilde{E}^{\prime})$ such that
$\tilde{G}^{\prime}$ admits a perfect matching and
$\tilde{w}(E^{\prime})\leq|V|$. For this purpose, we can assume that all the
edges of weight $0$ are included in $\tilde{E}^{\prime}$.

Let $\tilde{E}_{0}$ be the set of edges of weight $0$, and $\tilde{X}$ be the
set of edges of weight $1$ each of which is derived from an edge in the
Hamiltonian cycle $X$. We then observe that the subgraph
$(\tilde{V},\tilde{E}_{0}\cup\tilde{X})$ is connected since $X$ is a
Hamiltonian cycle in $G$. We also see
$\tilde{w}(\tilde{E}_{0}\cup\tilde{X})=|\tilde{X}|=2|V|$ as exactly two edges
in $\tilde{E}$ are derived from each edge in $E$. Since the two edges derived
from the same edge connect the same pair of connected components of
$\tilde{E}_{0}$, even if we remove one of them for each edge in $X$, the
resulting subgraph is still connected. Thus, in order to construct a desired
subgraph $\tilde{G}^{\prime}$, it suffices to choose one of the two edges for
each pair so that the chosen edges form a matching in $\tilde{G}$, which can
be extended to a perfect matching in $\tilde{G}$ by using edges in
$\tilde{E}_{0}$ (since exactly two edges in $X$ are incident to each $u\in V$,
exactly one of $\tilde{u}_{1},\tilde{u}_{2},\tilde{u}_{3}$ is exposed by the
matching formed by the chosen edges, which can be matched with
$\tilde{u}_{0}$).

Let $X=(x_{1},x_{2},\dots,x_{n},x_{1})$ and $s=x_{1}$. Without loss of
generality, we assume that $f_{s,1}=\\{x_{n},x_{1}\\}$ and
$f_{s,2}=\\{x_{1},x_{2}\\}$ are the two edges around $s$ traversed in this
order in $X$ (by shifting the indices of $f_{s,i}$ and by reversing the
indices of $X$ if necessary). Then, the two edges in $\tilde{G}$ corresponding
to $f_{s,1}$ are incident to $\tilde{s}_{2}$ and $\tilde{s}_{3}$, and those
corresponding to $f_{s,2}$ are incident to $\tilde{s}_{3}$ and
$\tilde{s}_{1}$. First, let us choose the latter edge $\tilde{e}_{1}$ incident
to $\tilde{s}_{1}$, which is disjoint from both edges corresponding to
$f_{s,1}$. For the remaining vertices $x_{k}$ $(k=2,3,\dots,n)$, in the
ascending order of $k$, we can choose one edge $\tilde{e}_{k}$ corresponding
to $\\{x_{k-1},x_{k}\\}$ so that $\tilde{e}_{k-1}$ and $\tilde{e}_{k}$ are
disjoint (as we always have two disjoint choices of $\tilde{e}_{k}$). Recall
that both edges corresponding to $f_{s,1}$ are disjoint from $\tilde{e}_{1}$,
which implies that $\tilde{e}_{n}$ and $\tilde{e}_{1}$ are also disjoint
(regardless of the choice of $\tilde{e}_{n}$). Thus, the chosen edges are
pairwise disjoint, i.e., they form a matching in $\tilde{G}$, and we are done.

Suppose that $\tilde{G}$ has a spanning tree $\tilde{T}$ containing a perfect
matching with $\tilde{w}(\tilde{T})\leq|V|$. Since
$|\tilde{T}|=|\tilde{V}|-1=4|V|-1$, it consists of at most $|V|$ edges of
weight $1$ and at least $3|V|-1$ edges of weight $0$. Let
$\tilde{T}_{1}\coloneq\\{\,e\in\tilde{T}\mid w(e)=1\,\\}$ and $T_{1}$ be the
set of edges in $E$ corresponding to the edges in $\tilde{T}_{1}$. Observe
that $T_{1}$ must be connected.

Let $\tilde{M}\subseteq\tilde{T}$ be a perfect matching. Then, for each vertex
$u\in V$, the corresponding center vertex $\tilde{u}_{0}\in\tilde{V}$ is
matched with an edge $\\{\tilde{u}_{0},\tilde{u}_{i}\\}$ $(i\in\\{1,2,3\\})$
of weight $0$, and the other two neighbors $\tilde{u}_{j}$ and $\tilde{u}_{k}$
$(j\neq i\neq k)$ are matched with edges of weight $1$. Since there are $2|V|$
such vertices in total and $|\tilde{T}_{1}|\leq|V|$, we must have
$\tilde{T}_{1}\subseteq\tilde{M}$ and $|\tilde{T}_{1}|=|V|$. That is, $T_{1}$
is a connected spanning subgraph of $G$ such that each vertex has its degree
exactly $2$, which is indeed a Hamiltonian cycle. ∎

For Statement 2b, we add the absent edges of $\tilde{G}$ by setting their
weight as $2$. Then, Claim 3.5 holds as it is (by replacing $\tilde{G}$ with
the augmented graph), because any perfect matching uses at least $|V|$ edges
of weight at least $1$.

##  4 On Strongly Balanced Spanning Trees (Proof of Theorem 2.3)

In this section, we prove Theorem 2.3. We remark that Lemma 2.1 implies the
following observation, which leads to the tractability of MinSBST for the
bipartite graphs with the aid of polynomial-time algorithms for the weighted
matroid intersection problem.

######  Observation 4.1 (cf. [11, Lemma 5] and [27, Lemma 3.6]).

For a balanced bipartite graph $G$, the set of strongly balanced spanning
trees of $G$ can be represented as the set of common bases of two matroids,
one of which is graphic and the other is (a truncation of) a partition
matroid.

In what follows, we prove the NP-hardness of SBST. The _incidence graph_ of a
$3$-CNF $\psi(x)=C_{1}\wedge C_{2}\wedge\cdots\wedge C_{m}$ on $n$ boolean
variables $x=(x_{1},x_{2},\dots,x_{n})$ is a bipartite graph defined as
follows: the vertex set is the set of variables and clauses, and an edge
exists between a variable $x_{i}$ and a clause $C_{j}$ if and only if $C_{j}$
contains a positive or negative literal of $x_{i}$. The 3-SAT problem is known
to be NP-complete even when the incidence graph of the input $3$-CNF is very
restricted.

######  Problem (Satisfiability of 3-CNF (3-SAT)).

Input:

A $3$-CNF $\psi(x)$ on $n$ boolean variables $x=(x_{1},x_{2},\dots,x_{n})$.

Goal:

Test whether there exists an assignment $a\in\\{0,1\\}^{n}$ such that
$\psi(a)=1$ or not.

######  Theorem 4.2 (Lichtenstein [23]).

3-SAT is NP-complete even if $\psi(x)$ is restricted so that the incidence
graph of $\psi(x)$ attached with a Hamiltonian cycle on the variables is
planar.

We prove Theorem 2.3 by reducing this restricted 3-SAT to SBST with the stated
restriction. Let $\psi(x)$ be a $3$-CNF $\psi(x)=C_{1}\wedge
C_{2}\wedge\cdots\wedge C_{m}$ on $n$ boolean variables
$x=(x_{1},x_{2},\dots,x_{n})$ whose incidence graph attached with a
Hamiltonian cycle $X$ on the variables is planar, and fix its planar
embedding. Without loss of generality, $X$ intersects
$x_{1},x_{2},\dots,x_{n}$ in this order. We construct from $\psi$ a subcubic
planar graph $G=(V,E)$ as follows (see Figures 2–4).

For each variable $x_{i}$ $(i=1,2,\dots,n)$, which appears in
$k_{i}^{\mathrm{in}}$ clauses lying inside of $X$ and in
$k_{i}^{\mathrm{out}}$ clauses lying outside of $X$ (under the planar
embedding of the incidence graph fixed above), create the following variable
gadget (see Figure 2). Create a cycle

$(u_{i},u^{\mathrm{in}}_{i,0},u^{\mathrm{in}}_{i,1},\bar{u}^{\mathrm{in}}_{i,1},\dots,u^{\mathrm{in}}_{i,k_{i}^{\mathrm{in}}},\bar{u}^{\mathrm{in}}_{i,k_{i}^{\mathrm{in}}},u_{i}^{\mathrm{T}},u_{i}^{\mathrm{F}},u^{\mathrm{out}}_{i,k_{i}^{\mathrm{out}}},\bar{u}^{\mathrm{out}}_{i,k_{i}^{\mathrm{out}}},\dots,u^{\mathrm{out}}_{i,1},\bar{u}^{\mathrm{out}}_{i,1},u^{\mathrm{out}}_{i,0},u_{i}).$

Then, add two vertices $u_{i,0}$ and $u_{i}^{\mathrm{end}}$ with four incident
edges $\\{u_{i,0},u^{\mathrm{in}}_{i,0}\\}$,
$\\{u_{i,0},u^{\mathrm{out}}_{i,0}\\}$,
$\\{u_{i}^{\mathrm{end}},u_{i}^{\mathrm{T}}\\}$, and
$\\{u_{i}^{\mathrm{end}},u_{i}^{\mathrm{F}}\\}$, and two vertices
$u^{\prime}_{i,0}$ and $u^{\prime\prime}_{i,0}$ with two incident edges
$\\{u_{i,0},u^{\prime}_{i,0}\\}$ and
$\\{u^{\prime}_{i,0},u^{\prime\prime}_{i,0}\\}$.

Figure 2: The variable gadget for a variable $x_{i}$. In any strongly balanced
spanning tree $T$ (if exists), the black vertices will be in $V_{T}^{+}$ (with
degree constraint $2$), the white vertices will be in $V_{T}^{-}$ (without
degree constraint), and the checkered vertices can be in either side,
alternately from $u_{i}$; the lower figure illustrates a subtree corresponding
to an assignment with $x_{i}=1$.

We connect those variable gadgets as Figure 3. Specifically, for each
$i=1,2,\dots,n-1$, we introduce a joint vertex $u_{i,i+1}$ with two incident
edges $\\{u_{i}^{\mathrm{end}},u_{i,i+1}\\}$ and $\\{u_{i,i+1},u_{i+1}\\}$,
and put a vertex $u_{n,n+1}$ with an incident edge
$\\{u_{n}^{\mathrm{end}},u_{n,n+1}\\}$ at the end. Furthermore, at the
beginning (before $u_{1}$), we put a tree consisting of eight vertices as
illustrated, whose three leaves are named as $s_{1},s_{2},s_{3}$.

Figure 3: The whole structure of the variable gadgets. In any strongly
balanced spanning tree $T$ (if exists), the black vertices will be in
$V_{T}^{+}$ (with degree constraint $2$ except for $s_{1}$, which will be the
unique leaf in $V_{T}^{+}$) and the white vertices will be in $V_{T}^{-}$
(without degree constraint).

Finally, for each clause $C_{j}=(y_{j,1}\vee y_{j,2}\vee y_{j,3})$, create a
clause gadget as follows (see Figure 4). Create a cycle
$(c_{j,1},c_{j,12},c_{j,2},c_{j,23},c_{j,3},c_{j,31},c_{j,1})$, and add two
vertices $c_{j}$ and $c^{\prime}_{j}$ with two incident edges
$\\{c_{j},c^{\prime}_{j}\\}$ and $\\{c^{\prime}_{j},c_{j,31}\\}$. For each
$\ell=1,2,3$, add an edge between $c_{j,\ell}$ and $b_{j,\ell}$, where
$b_{j,\ell}$ is a vertex in a variable gadget that is determined depending on
whether $C_{j}$ lies inside or outside of $X$ and what literal $y_{j,\ell}$ is
as follows. Suppose that $C_{j}$ lies inside of $X$, and that $y_{j,\ell}$ is
a positive literal of a variable $x_{i}$. Then,
$b_{j,\ell}=u_{i,k}^{\mathrm{in}}$, where $1\leq k\leq k_{i}^{\mathrm{in}}$ is
such that $y_{j,\ell}$ is the $k$-th appearance of $x_{i}$ in clauses lying
inside of $X$ along the cycle $X=(x_{1},x_{2},\dots,x_{n},x_{1})$. The other
three cases are analogous; if $C_{j}$ lies outside of $X$, then replace the
superscripts ${\bullet}^{\mathrm{in}}$ with ${\bullet}^{\mathrm{out}}$, and if
$y_{j,\ell}$ is a negative literal of $x_{i}$, then replace $u_{i}$ with
$\bar{u}_{i}$.

Figure 4: The clause gadget for a clause $C_{j}=(y_{j,1}\vee y_{j,2}\vee
y_{j,3})$. In any strongly balanced spanning tree $T$ (if exists), the black
vertices will be in $V_{T}^{+}$ (with degree constraint $2$), the white
vertices will be in $V_{T}^{-}$ (without degree constraint), and the checkered
vertices can be in either side depending on the situation in the corresponding
variable gadgets; the right figure illustrates an example of a subtree
corresponding to the situation when $C_{j}$ is satisfied by $y_{j,2}=1$.

The resulting graph $G=(V,E)$ is clearly subcubic and planar. The following
claim completes the proof of Theorem 2.3.

######  Claim 4.3.

$\psi$ is satisfiable if and only if $G$ has a strongly balanced spanning
tree.

###### Proof.

Suppose that $a=(a_{1},a_{2},\dots,a_{n})\in\\{0,1\\}^{n}$ satisfies $\psi$.
Then, we can construct a strongly balanced spanning tree $T$ of $G$ as follows
(see also Figures 2–4).

For each variable $x_{i}\ (=a_{i})$, we construct a spanning tree in the
corresponding variable gadget by deleting three edges; we delete
$\\{u_{i},u_{i,0}^{\mathrm{in}}\\}$, $\\{u_{i,0},u_{i,0}^{\mathrm{out}}\\}$,
and $\\{u_{i}^{\mathrm{F}},u_{i}^{\mathrm{end}}\\}$ if $a_{i}=1$ (cf. Figure
2), and we delete $\\{u_{i},u_{i,0}^{\mathrm{out}}\\}$,
$\\{u_{i,0},u_{i,0}^{\mathrm{in}}\\}$, and
$\\{u_{i}^{\mathrm{T}},u_{i}^{\mathrm{end}}\\}$ if $a_{i}=0$. Under the
assumption that $u_{i}\in V_{T}^{+}$, in the former case (when $a_{i}=1$), all
the vertices $u_{i,k}^{\bullet}$ $(k\geq 1,\
\bullet\in\\{\mathrm{in},\mathrm{out}\\})$ and $u_{i}^{\mathrm{T}}$ are in
$V_{T}^{-}$ (i.e., without degree constraint), and all the vertices in the
form $\bar{u}_{i,k}^{\bullet}$ $(k\geq 1,\
\bullet\in\\{\mathrm{in},\mathrm{out}\\})$ and $u_{i}^{\mathrm{F}}$ are in
$V_{T}^{+}$ with exactly two incident edges in this gadget; in the latter case
(when $a_{i}=0$), $V_{T}^{+}$ and $V_{T}^{-}$ are interchanged. Also, in
either case, we have $u_{i}^{\mathrm{end}}\in V_{T}^{+}$ (under the assumption
that $u_{i}\in V_{T}^{+}$).

We connect those spanning trees of the variable gadgets by taking all the
edges connecting them including the tree at the beginning and the leaf at the
end (illustrated in Figure 3). Here, note that $s_{1},s_{2},s_{3}$ must be
leaves in $T$, and $s_{2}$ and $s_{3}$ are on the same side of the bipartition
$(V_{T}^{+},V_{T}^{-})$, which is different from $s_{1}$. This forces $s_{1}$
to be a unique leaf in $V_{T}^{+}$. As a result, inductively, $u_{i}$ and
$u_{i}^{\mathrm{end}}$ $(i=1,2,\dots,n)$ are all in $V_{T}^{+}$.

Finally, for each clause $C_{j}=(y_{j,1}\vee y_{j,2}\vee y_{j,3})$, pick one
of the literals $y_{j,\ell}$ whose value is $1$ in the assignment $x=a$. Then,
take an edge $\\{b_{j,\ell},c_{j,\ell}\\}$ and all but one edge incident to
$c_{j,\ell}$ in the corresponding clause gadget (cf. Figure 4). This results
in a spanning tree of the clause gadget connected to the variable gadgets with
the bridge $\\{b_{j,\ell},c_{j,\ell}\\}$. By the above observation and
assumption, we have $b_{j,\ell}\in V_{T}^{-}$. We then have
$c_{j,1},c_{j,2},c_{j,3},c^{\prime}_{j}\in V_{T}^{+}$, and these vertices
indeed have degree $2$ in the resulting tree.

Overall, we have indeed constructed a desired, strongly balanced spanning tree
of $G$.

Suppose that $G$ has a strongly balanced spanning tree $T$. We show that $T$
should be in the form constructed above, which implies that we can reconstruct
an assignment $a=(a_{1},a_{2},\dots,a_{n})$ satisfying $\psi$.

The main task is to confirm that for any clause gadget plus its three
neighbors $b_{j,1},b_{j,2},b_{j,3}$, the restriction of $T$ there does not
contain a path between two of the neighbors; that is, any clause gadget does
not play the role of connecting variable gadgets. Observe that $T$ must
contain the two edges incident to $c^{\prime}_{j}$, and $c_{j}\in V_{T}^{-}$,
$c^{\prime}_{j}\in V_{T}^{+}$, and $c_{j,31}\in V_{T}^{-}$. By connectivity,
at least one of $\\{c_{j,1},c_{j,31}\\}$ and $\\{c_{j,3},c_{j,31}\\}$ is in
$T$.

Suppose that there exists a path between $b_{j,1}$ and $b_{j,3}$. Since
$\\{c_{j,1},c_{j,31}\\}$ or $\\{c_{j,3},c_{j,31}\\}$ is in $T$ and then
$c_{j,1}$ or $c_{j,3}$, respectively, is in $V_{T}^{+}$, the path must be
$(b_{j,1},c_{j,1},c_{j,31},c_{j,3},b_{j,3})$ and $c_{j,1},c_{j,3}\in
V_{T}^{+}$. Then, neither $\\{c_{j,1},c_{j,12}\\}$ nor
$\\{c_{j,3},c_{j,23}\\}$ is in $T$, and hence $\\{c_{j,2},c_{j,12}\\}$ and
$\\{c_{j,2},c_{j,23}\\}$ must be in $T$. Also, as $T$ is connected,
$\\{c_{j,2},b_{j,2}\\}$ must be in $T$. This, however, cannot satisfy the
degree constraint no matter which $c_{j,12}$ (degree $1$) or $c_{j,2}$ (degree
$3$) is in $V_{T}^{+}$, a contradiction.

Suppose that there exists a path between $b_{j,1}$ and $b_{j,2}$. If the path
is via $c_{j,13}$, then $c_{j,1},c_{j,2}\in V_{T}^{+}$ and hence neither of
$\\{c_{j,1},c_{j,12}\\}$ and $\\{c_{j,2},c_{j,12}\\}$ is in $T$; then
$c_{j,12}$ is isolated, a contradiction. Otherwise, the path is
$(b_{j,1},c_{j,1},c_{j,12},c_{j,2},b_{j,2})$. In this case, $T$ must contain
$\\{c_{j,3},c_{j,31}\\}$ and hence $c_{j,3}\in V_{T}^{+}$. If
$\\{c_{j,3},c_{j,23}\\}$ is in $T$, then $\\{c_{j,3},b_{j,3}\\}$ cannot be in
$T$ by the degree constraint, and hence $\\{c_{j,2},c_{j,23}\\}$ is also in
$T$ as $T$ is connected. This, however, violates the degree constraint of
$c_{j,2}\in V_{T}^{+}$, a contradiction. Otherwise, $\\{c_{j,3},c_{j,23}\\}$
is not in $T$, and then $\\{c_{j,2},c_{j,23}\\}$ is in $T$ again as $T$ is
connected. This, however, cannot satisfy the degree constraint no matter which
$c_{j,2}$ (degree $3$) or $c_{j,23}$ (degree $1$) is in $V_{T}^{+}$, a
contradiction.

Thus, we have confirmed that any clause gadget does not connect variable
gadgets. Note that $T$ may contain two or three of $\\{c_{j,1},b_{j,1}\\}$,
$\\{c_{j,2},b_{j,2}\\}$, and $\\{c_{j,3},b_{j,3}\\}$, and then the end vertex
$b_{j,\ell}$ with $\\{c_{j,\ell},b_{j,\ell}\\}$ contained in $T$ must be in
$V_{T}^{-}$ due to the degree constraint. Also, no matter how many such edges
are contained in $T$, exactly one of them is extended to $c_{j}$.

Next, let us consider variable gadgets. By the above observation, they must be
connected with the edges illustrated in Figure 3, which inductively forces
that $u_{i}$ and $u_{i}^{\mathrm{end}}$ $(i=1,2,\dots,n)$ are both in
$V_{T}^{+}$ as follows.

For each variable gadget, due to the form of the eight-vertex tree at the
beginning $(i=1)$ or by the induction hypothesis $(i\geq 2)$, we have
$u_{i}\in V_{T}^{+}$ and $T$ contains exactly one edge incident to $u_{i}$ not
in the variable gadget. Then, exactly one of
$\\{u_{i},u_{i,0}^{\mathrm{in}}\\}$ and $\\{u_{i},u_{i,0}^{\mathrm{out}}\\}$
must be contained in $T$, and then $u_{i,0}^{\mathrm{in}}$ or
$u_{i,0}^{\mathrm{out}}$, respectively, is in $V_{T}^{-}$. As with the clause
gadgets, observe that $T$ must contain the two edges incident to
$u^{\prime}_{i,0}$, and $u^{\prime\prime}_{i,0}\in V_{T}^{-}$,
$u^{\prime}_{i,0}\in V_{T}^{+}$, and $u_{i,0}\in V_{T}^{-}$. By connectivity,
$\\{u_{i,0},u_{i,0}^{\mathrm{in}}\\}$ or
$\\{u_{i,0},u_{i,0}^{\mathrm{out}}\\}$ is in $T$, and then
$u_{i,0}^{\mathrm{in}}$ or $u_{i,0}^{\mathrm{out}}$, respectively, is in
$V_{T}^{+}$. Thus, we have exactly two possible choices here such that exactly
one of $u_{i,0}^{\mathrm{in}}$ and $u_{i,0}^{\mathrm{out}}$ is in $V_{T}^{+}$
and the other is in $V_{T}^{-}$. By connectivity again, the two paths
$(u_{i,0}^{\mathrm{in}},u_{i,1}^{\mathrm{in}},\bar{u}_{i,1}^{\mathrm{in}},\dots,u_{i,k_{i}^{\mathrm{in}}}^{\mathrm{in}},\bar{u}_{i,k_{i}^{\mathrm{in}}}^{\mathrm{in}},u_{i}^{\mathrm{T}})$
and
$(u_{i,0}^{\mathrm{out}},\bar{u}_{i,1}^{\mathrm{out}},u_{i,1}^{\mathrm{out}},\dots,\bar{u}_{i,k_{i}^{\mathrm{out}}}^{\mathrm{out}},u_{i,k_{i}^{\mathrm{out}}}^{\mathrm{out}},u_{i}^{\mathrm{F}})$
are completely included in $T$. Due to the parity, $T$ cannot contain both
edges $\\{u_{i}^{\mathrm{T}},u_{i}^{\mathrm{end}}\\}$ and
$\\{u_{i}^{\mathrm{F}},u_{i}^{\mathrm{end}}\\}$, and hence exactly one of them
in addition to $\\{u_{i}^{\mathrm{T}},u_{i}^{\mathrm{F}}\\}$ is contained in
$T$. Then, due to the degree constraint, we obtain $u_{i}^{\mathrm{end}}\in
V_{T}^{+}$, which forces $u_{i,i+1}\in V_{T}^{-}$ and $u_{i+1}\in V_{T}^{+}$
(when $i<n$).

Overall, in the variable gadget, there are exactly two possible spanning
trees, from which an assignment $a$ with $\psi(a)=1$ can be reconstructed.
This completes the proof. ∎

##  5 Concluding Remarks

We have investigated two problems on a fusion of two fundamental combinatorial
structures, a spanning tree and a perfect matching.

The first problem, finding a minimum-weight spanning tree containing a perfect
matching, has been shown as tractable in the very restricted situation when
the graph is complete (or complete bipartite) and the edge weights take at
most two values. It, however, becomes NP-hard if we relax one of the two
conditions. For this problem, it seems reasonable to consider nontrivial
approximation or fixed-parameter algorithms.

The second problem, testing the existence of a strongly balanced spanning
tree, has turned out NP-hard even if the input graph is subcubic and planar.
In the reduction, we have introduced many artificial leaves, which have played
the important role to force which vertices should be on which side of the
resulting bipartition. This can be somewhat relaxed by replacing each leaf
with a five-vertex gadget as in Figure 5 so that the resulting graph is still
subcubic and planar and has no leaf. An interesting open question is the
following: is it possible to strengthen “subcubic” to “cubic”? Or, possibly,
is this problem for the cubic graphs in fact tractable? It seems also
interesting to consider the tractability for relatively dense graphs, which
tend to have a solution.

Figure 5: An alternative five-vertex gadget for each leaf. The lower vertex
$\ell$ corresponds to an original leaf. In any strongly balanced spanning tree
$T$ (if exists), the black vertices will be in $V_{T}^{+}$ (with degree
constraint $2$), and the white vertices will be in $V_{T}^{-}$ (without degree
constraint), except for exactly one of these gadgets (that corresponds to
$s_{1}$ in Figure 3).

## References

  * [1] Takanori Akiyama, Takao Nishizeki, and Nobuji Saito.  NP-completeness of the Hamiltonian cycle problem for bipartite graphs.  Journal of Information Processing, 3(2):73–76, 1980.
  * [2] Carl Brezovec, Gérard Cornuéjols, and Fred Glover.  Two algorithms for weighted matroid intersection.  Mathematical Programming, 36(1):39–53, 1986.
  * [3] Lei Chen, Changhong Lu, and Zhenbing Zeng.  Labelling algorithms for paired-domination problems in block and interval graphs.  Journal of Combinatorial Optimization, 19(4):457–470, 2010.
  * [4] Artur Czumaj and Willy-Bernhard Strothmann.  Bounded degree spanning trees.  In 5th Annual European Symposium on Algorithms (ESA), pages 104–117, 1997.
  * [5] Edsger W. Dijkstra.  A note on two problems in connexion with graphs.  Numerische Mathematik, 1:269–271, 1959.
  * [6] Ran Duan, Hongxun Wu, and Renfei Zhou.  Faster matrix multiplication via asymmetric hashing.  In 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 2129–2138. IEEE, 2023.
  * [7] Jack Edmonds.  Maximum matching and a polyhedron with 0, 1-vertices.  Journal of Research of the National Bureau of Standards B, 69(125-130):55–56, 1965.
  * [8] Jack Edmonds.  Paths, trees, and flowers.  Canadian Journal of Mathematics, 17:449–467, 1965.
  * [9] Jack Edmonds.  Matroid intersection.  Annals of Discrete Mathematics, 4:39–49, 1979.
  * [10] András Frank.  Connections in Combinatorial Optimization.  Oxford University Press, 2011.
  * [11] András Frank, Eberhard Triesch, Bernhard Korte, and Jens Vygen.  On the bipartite travelling salesman problem.  Technical report, Technical Report 98866-OR, Research Institute for Discrete Mathematics, 1998.
  * [12] Satoru Fujishige.  Submodular Functions and Optimization.  Elsevier, 2005.
  * [13] Martin Furer and Balaji Raghavachari.  Approximating the minimum-degree steiner tree to within one of optimal.  Journal of Algorithms, 17(3):409–423, 1994.
  * [14] Michel X. Goemans.  Minimum bounded degree spanning trees.  In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 273–282. IEEE, 2006.
  * [15] Nicholas J.A. Harvey.  Algebraic algorithms for matching and matroid problems.  SIAM Journal on Computing, 39(2):679–702, 2009.
  * [16] Refael Hassin and Asaf Levin.  Minimum restricted diameter spanning trees.  Discrete Applied Mathematics, 137(3):343–357, 2004.
  * [17] Refael Hassin and Arie Tamir.  On the minimum diameter spanning tree problem.  Information Processing Letters, 53(2):109–111, 1995.
  * [18] Teresa W. Haynes and Peter J. Slater.  Paired-domination in graphs.  Networks, 32(3):199–206, 1998.
  * [19] Masao Iri and Nobuaki Tomizawa.  An algorithm for finding an optimal “independent assignment”.  Journal of the Operations Research Society of Japan, 19(1):32–57, 1976.
  * [20] Joseph B. Kruskal.  On the shortest spanning subtree of a graph and the traveling salesman problem.  Proceedings of the American Mathematical Society, 7(1):48–50, 1956\.
  * [21] Eugene L. Lawler.  Optimal matroid intersections.  In Combinatorial Structures and Their Applications, pages 233–234. Gorden and Breach, 1970.
  * [22] Eugene L. Lawler.  Matroid intersection algorithms.  Mathematical Programming, 9(1):31–56, 1975.
  * [23] David Lichtenstein.  Planar formulae and their uses.  SIAM Journal on Computing, 11(2):329–343, 1982.
  * [24] Xiaoxu Ma and Yujun Yang.  Enumeration of spanning trees containing perfect matchings in hexagonal chains with a unique kink.  Applied Mathematics and Computation, 475:128722, 2024.
  * [25] Silvio Micali and Vijay V. Vazirani.  An $\mathrm{O}(\sqrt{|V|}|{E}|)$ algorithm for finding maximum matching in general graphs.  In 21st Annual Symposium on Foundations of Computer Science (FOCS), pages 17–27. IEEE, 1980.
  * [26] Kazuo Murota.  Discrete Convex Analysis.  SIAM, 2003.
  * [27] Ryoma Norose and Yutaro Yamaguchi.  Approximation and FPT algorithms for finding DM-irreducible spanning subgraphs.  arXiv:2404.17927, 2024.
  * [28] Robert C. Prim.  Shortest connection networks and some generalizations.  The Bell System Technical Journal, 36(6):1389–1401, 1957.
  * [29] Alexander Schrijver.  Combinatorial Optimization: Polyhedra and Efficiency.  Springer, 2003.
  * [30] Mohit Singh and Lap Chi Lau.  Approximating minimum bounded degree spanning trees to within one of optimal.  Journal of the ACM, 62(1), 2015.
  * [31] Michael J. Spriggs, J. Mark Keil, Sergei Bespamyatnikh, Michael Segal, and Jack Snoeyink.  Computing a $(1+\varepsilon)$-approximate geometric minimum-diameter spanning tree.  Algorithmica, 38(4):577–589, 2004.
  * [32] Vikash Tripathi, Ton Kloks, Arti Pandey, Kaustav Paul, and Hung-Lung Wang.  Complexity of paired domination in AT-free and planar graphs.  Theoretical Computer Science, 930:53–62, 2022.
  * [33] Vijay V. Vazirani.  A theory of alternating paths and blossoms from the perspective of minimum length.  Mathematics of Operations Research, 2024.
  * [34] Damir Vukiěević and Nenad Trinajstić.  On the anti-forcing number of benzenoids.  Journal of Mathematical Chemistry, 42:575–583, 2007.
  * [35] Baoyindureng Wu and Heping Zhang.  Graphs where each spanning tree has a perfect matching.  Contributions to Discrete Mathematics, 16(3):1–8, 2021.


#
Sturm’s Theorem with Endpoints

Philippe Pébay1 J. Maurice Rojas2 David C. Thompson1

###### Abstract

Sturm’s Theorem is a fundamental 19${}^{\text{\text@underline{th}}}$ century
result relating the number of real roots of a polynomial $f$ in an interval to
the number of sign alternations in a sequence of polynomial division-like
calculations. We provide a short direct proof of Sturm’s Theorem, including
the numerically vexing case (ignored in many published accounts) where an
interval endpoint is a root of $f$.

11footnotetext:  Sandia National Laboratories, e-mail<EMAIL_ADDRESS>,
<EMAIL_ADDRESS>. 22footnotetext:  Department of Mathematics, Texas A&M
University TAMU 3368, College Station, Texas 77843-3368, USA. e-mail:
<EMAIL_ADDRESS>, web page: www.math.tamu.edu/~rojas . Partially supported
by NSF CAREER grant DMS-0349309, and Sandia National Laboratories.

##  1 Introduction

Counting the number of roots of a polynomial in an interval is a fundamental
algorithmic problem in real algebraic geometry, and forms the core of
techniques for deeper problems such as real-solving and the first order theory
of the reals. On the practical side, numerous problems from control theory and
physical modeling reduce to solving systems of polynomial equations over the
real numbers, and one can not solve a system numerically until one understands
how to count the number of roots in an interval.

We will present, from scratch, a strengthened version of a classical result of
Sturm. To begin, let us review some basic ideas.

###### Notation

Recall that $\mathbb{R}[x_{1}]$ is the collection of all polynomials in the
variable $x_{1}$ with real coefficients. For any $f\\!\in\\!\mathbb{R}[x_{1}]$
of degree $d$ we then define its pseudo-remainder sequence (a.k.a. Sturm
sequence) to be $P_{f}\\!:=\\!(p_{0},\ldots,p_{d})$, where $p_{0}\\!:=\\!f$,
$p_{1}\\!:=\\!f^{\prime}$ (the derivative of $f$),
$p_{i}\\!:=\\!q_{i+1}p_{i+1}-p_{i+2}$ for all $i\\!\in\\!\\{0,\ldots,d-2\\}$,
and $q_{i+1}$ and $-p_{i+2}$ are respectively the quotient and remainder
obtained from dividing $p_{i}$ by $p_{i+1}$. We also define
$P_{f}(c)\\!:=\\!(p_{0}(c),\ldots,p_{d}(c))$ for any $c\\!\in\\!\mathbb{R}$
and $V_{f}(c)$ to be the number of sign alternations in the sequence
$P_{f}(c)$. In particular, the number of sign alternations in an arbitrary
sequence $(s_{0},\ldots,s_{d})$ is simply the number of
$j\\!\in\\!\\{0,\ldots,d-1\\}$ such that there is a $k\\!>\\!0$ with
$s_{j}s_{j+k}\\!<\\!0$ and $s_{\ell}\\!=\\!0$ for all $\ell$ with
$j\\!<\\!\ell\\!<\\!j+k$. Finally, we let
$\sigma:\mathbb{R}\longrightarrow\\{-1,0,1\\}$ be the sign function, which
maps all positive (resp. negative) numbers to $1$ (resp. $-1$) and $0$ to $0$.
We also naturally extend $\sigma$ to sequences by
$\sigma(s)\\!:=\\!(\sigma(s_{0}),\ldots,\sigma(s_{d}))$. $\diamond$

###### Example 1.1

For $f(x_{1})\\!:=\\!x^{4}_{1}-2x^{2}_{1}+1$, we clearly obtain
$P_{f}(x_{1})\\!=\\!(x^{4}_{1}-2x^{2}_{1}+1,4x^{3}_{1}-4x_{1},x^{2}_{1}-1,0,0)$,
$\sigma(P_{f}(-2))\\!=\\!(1,-1,1)$, $\sigma(P_{f}(0))\\!=\\!(1,0,-1)$, and
thus $V_{f}(-2)\\!=\\!2$ and $V_{f}(0)\\!=\\!1$. Note also that $-1$ is the
only root of $f$ in the half-open interval $(-2,1]$, and that Sturm sequences
can terminate with more than one zero term. $\diamond$

Recall that a root $\zeta$ of $f$ is a multiple (or degenerate) root iff
$f(\zeta)\\!=\\!f^{\prime}(\zeta)\\!=\\!0$. Roots $\zeta$ with
$f^{\prime}(\zeta)\\!\neq\\!0$ are usually called simple or non-degenerate.

######  Theorem 1.2 (Refined Sturm’s Theorem)

For any $f\\!\in\\!\mathbb{R}[x_{1}]\\!\setminus\\!\\{0\\}$ and any real
numbers $a$ and $b$ with $a\\!\leq\\!b$, let $N_{f}(a,b]$ denote the
number111This theorem counts distinct roots and thus does not count multiple
roots more than once.  of roots of $f$ in the half-open interval
$(a,b]$.222When $a\\!<\\!b$ this half open interval includes $b$ but does not
include $a$, and we use the convention $(a,a]\\!=\\!\emptyset$. European
authors frequently use $]a,b]$ for what we call $(a,b]$.  Then

  1. 1.

If neither $a$ nor $b$ are multiple roots, then
$N_{f}(a,b]\\!=\\!V_{f}(a)-V_{f}(b)$.

  2. 2.

If $f(c)\\!=\\!f^{\prime}(c)\\!=\\!0$ then $V_{f}(c)\\!=\\!0$.

Note in particular that we can count roots in $(a,b]$ even when one or both
endpoints are roots of $f$ — provided no multiple roots occur at either
endpoint. Assertion (2), while almost trivial to prove, is the main reason one
needs to avoid multiple roots at end-points when using Sturm’s Theorem: The
information carried by the sign alternations of $P_{f}(c)$ is lost entirely
when $c$ is a multiple root.

###### Example 1.3

It is easily checked that the roots of
$f(x_{1})\\!:=\\!x^{3}_{1}-5x^{2}_{1}+7x_{1}-3$ are precisely $\\{2,3\\}$,
with $2$ a multiple root and $1$ a simple root, and that
$P_{f}(x_{1})\\!=\\!\left(x^{3}_{1}-5x^{2}_{1}+7x_{1}-3,3x^{2}_{1}-10x_{1}+7,\frac{8}{9}x_{1}-\frac{8}{9},0\right)$.
Clearly then, $V_{f}(1)\\!=\\!0$, $V_{f}(2)\\!=\\!1$, and $V_{f}(3)\\!=\\!0$,
so Sturm’s Theorem is confirmed for the interval $(2,3]$. However, we also see
that Sturm’s Theorem can not be applied to the interval $(1,3]$ since
$V_{f}(1)-V_{f}(3)\\!=\\!0$ and $f$ in fact still has a root in $(1,3]$.
$\diamond$

Curiously, most published accounts of Sturm’s Theorem avoid considering the
presence of any kind of root at an endpoint. Furthermore, many accounts assume
that $f$ has only simple roots. In practice, such an assumption can only be
enforced by computing square-free parts — a potentially wasteful (and
numerically unstable) computation, especially when speed is critical.

The proof of Sturm’s Theorem is elementary, but is frequently derived as a
consequence of more intricate constructions. Considering its deep importance
in numerical software, we present a short direct proof. The theorem follows
easily from a single lemma.

###### Lemma 1.4

Suppose $f\\!\in\\!\mathbb{R}[x_{1}]$ has positive degree $d$, and
$c\\!\in\\!\mathbb{R}$. Then the following properties hold for the Sturm
sequence $P_{f}(c)\\!=\\!(p_{0}(c),\ldots,p_{d}(c))$:

  1. 1.

(Sign Alternation Over a Simple Root) Suppose $p_{0}(c)\\!=\\!0$ and
$p_{1}(c)\\!\neq\\!0$. Then for all $\varepsilon\\!>\\!0$ sufficiently small,
$\sigma(p_{0}(c-\varepsilon))\\!=\\!-\sigma(p_{1}(c-\varepsilon))$ and
$\sigma(p_{0}(c+\varepsilon))\\!=\\!\sigma(p_{1}(c+\varepsilon))$.

  2. 2.

(Stability Under Common Multiples) Suppose $p_{0}$ and $p_{1}$ are each
divisible by $g\\!\in\\!\mathbb{R}[x_{1}]$. Then
$P_{f}\\!=\\!\frac{1}{g}P_{f/g}$.

  3. 3.

(Matching Sign Flips Over a Simple Node) Suppose $p_{i}(c)\\!=\\!0$ and
$p_{i+1}(c)\\!\neq\\!0$ for some $i\\!\geq\\!1$. Then
$\sigma(p_{i-1}(c))\\!=\\!-\sigma(p_{i+1}(c))$. Furthermore, for all
$\varepsilon\\!>\\!0$ sufficiently small,
$\sigma(p_{i-1}(c-\varepsilon))\\!=\\!-\sigma(p_{i+1}(c-\varepsilon))$ and
$\sigma(p_{i-1}(c+\varepsilon))\\!=\\!-\sigma(p_{i+1}(c+\varepsilon))$.

  4. 4.

(Propagation of Zeroes) For any $i\\!\in\\!\\{0,\ldots,d-2\\}$,
$p_{i}(c)\\!=\\!p_{i+1}(c)\\!=\\!0$ implies that $p_{j}(c)\\!=\\!0$ for all
$j\\!\geq\\!i+2$.

We are now ready to prove our refined version of Sturm’s Theorem.
Proof of Theorem 1.2:

Assertion (2): Since $p_{0}(c)\\!=\\!f(c)$ and $p_{1}(c)\\!=\\!f^{\prime}(c)$,
the recurrence defining the Sturm sequence immediately implies that
$p_{j}(c)\\!=\\!0$ for all all $j\\!\geq\\!2$, so we are done.

Assertion (1): If $a\\!=\\!b$, or $f$ is a nonzero constant, then we clearly
have $N_{f}(a,b]\\!=\\!V_{f}(a)-V_{f}(b)\\!=\\!0$ and Assertion (1) indeed
holds. So let us assume $a\\!<\\!b$ and that $f$ has positive degree $d$.

Let us now reduce to the special case where the following condition holds:
($\star$) $(a,b]$ contains at most $1$ root of $f$, with $b$ non-degenerate if
it is a root of $f$.
To do so, suppose first that $f$ has roots in $(a,b]$ and that, in strictly
increasing order, they are exactly $\zeta_{1},\ldots,\zeta_{m}$. Letting
$(c_{1},\ldots,c_{m})$ be any sequence satisfying
$a\\!<\\!c_{1}\\!<\\!\zeta_{1}\\!<\\!c_{2}\\!<\\!\zeta_{2}\\!<\cdots<\\!c_{m}\\!<\\!\zeta_{m}\\!\leq\\!b$,
we then see that $V_{f}(a)-V_{f}(b)$ is exactly
$(V_{f}(a)-V_{f}(c_{1}))+(V_{f}(c_{1})-V_{f}(c_{2}))+\cdots+(V_{f}(c_{m-1})-V_{f}(c_{m}))+(V_{f}(c_{m})-V_{f}(b))$.
Since, by definition, $N_{f}(a,b]$ is exactly
$N_{f}(a,c_{1}]\hskip 19.91684pt+\hskip 19.91684ptN_{f}(c_{1},c_{2}]\hskip
17.07182pt+\hskip 5.69046pt\cdots\hskip 5.69046pt+\hskip
11.38092ptN_{f}(c_{m-1},c_{m}]\hskip 14.22636pt+\hskip
14.22636ptN_{f}(c_{m},b]$
it then clearly suffices to prove
$N_{f}(a,c_{1}]\\!=\\!V_{f}(a)-V_{f}(c_{1})$,
$N_{f}(c_{1},c_{2}]\\!=\\!V_{f}(c_{1})-V_{f}(c_{2})$, …,
$N_{f}(c_{m-1},c_{m}]\\!=\\!V_{f}(c_{m-1})-V_{f}(c_{m})$, and
$N_{f}(c_{m},b]\\!=\\!V_{f}(c_{m})-V_{f}(b)$. In other words, whether or not
$f$ has roots in $(a,b]$, we can indeed assume Condition ($\star$).

Let us now reduce even further to the special case where the following
slightly stronger condition holds:
($\star\star$) $(a,b]$ contains at most $1$ root of $f$, and any root of $f$
in $(a,b]$ is simple.
To do so, observe that $g\\!:=\\!\gcd(f,f^{\prime})\\!\in\\!\mathbb{R}[x_{1}]$
and, for all $i\\!\in\\!\\{1,\ldots,m\\}$, $f/g$ is divisible by $x-\zeta_{i}$
but not divisible by $(x-\zeta_{i})^{2}$. (The latter fact follows easily from
the product rule for differentation.) So $f$ and $f/g$ have the same real
roots, except that all the real roots of $f/g$ are simple. By Assertion (2) of
Lemma 1.4 we then obtain $\sigma(P_{f}(c)g(c))\\!=\\!\sigma(P_{f/g}(c))$ and
thus $\sigma(P_{f}(c))\\!=\\!\sigma(g(c))\sigma(P_{f/g}(c))$ for all real $c$.
In particular, $V_{f}(c)\\!=\\!V_{f/g}(c)$ as long as $c$ is not a multiple
root. Since we are assuming that neither $a$ nor $b$ are multiple roots, we
can then clearly assume ($\star\star$).

We are now nearly done: Thanks to Condition ($\star\star$), the case where
$(a,b]$ contains a unique root $\zeta$ follows immediately from Assertion (1)
of Lemma 1.4, assuming we have proved the case where $(a,b]$ contains no roots
of $f$. For then we obtain
$N_{f}(a,b]\\!=\\!N_{f}(a,\zeta-\varepsilon]+N_{f}(\zeta-\varepsilon,\zeta+\varepsilon]+N_{f}(\zeta+\varepsilon,b]\\!=\\!0+1+0$,
where $\varepsilon\\!>\\!0$ is sufficiently small.

The final case where $(a,b]$ has no roots requires only one more refinement:
In our preceding subdivision used to enforce Condition ($\star$), suppose we
picked more $c_{i}$, so that the roots of $p_{1},\ldots,p_{d}$ (as well as
those of $p_{0}\\!=\\!f$) were also interlaced. Via the same trick of
cancellations in an alternating sum, we can thus reduce even further to the
special case where $(a,b]$ contains no roots of $f$ and contains at most $1$
root of $p_{1}\cdots p_{d}$. By Assertion (3) of Lemma 1.4, we are done.
$\blacksquare$

Proof of Lemma 1.4: Assertions (2) and (4) follow immediately from the
recurrence defining the Sturm sequence. Indeed, upon noting that every $p_{i}$
is a polynomial linear combination of $p_{0}$ and $p_{1}$, it is clear that
$g|p_{0}$ and $g|p_{1}$ together imply that every $p_{i}$ is divisible by $g$.
Assertion (2) then follows immediately from the uniqueness of remainders in
polynomial division. For Assertion (4) one merely proceeds by induction.

To prove Assertion (1) note that if $f^{\prime}(c)\\!=\\!p_{1}(c)\\!>\\!0$
(resp. $f^{\prime}(c)\\!=\\!p_{1}(c)\\!<\\!0$) then $f\\!=\\!p_{0}$ is locally
increasing (resp. decreasing) at $c$. Since the sign of $p_{1}$ is locally
constant at $c$, Assertion (1) follows immediately.

Assertion (3) follows easily upon observing that $p_{i}(c)\\!=\\!0$ implies
that $p_{i-1}(c)=-p_{i+1}(c)$, thanks to the recurrence defining the Sturm
sequence. In particular, one need only observe that the signs of $p_{i-1}$ and
$p_{i+1}$ are locally constant at $c$, so
$\sigma(p_{i-1}(c-\varepsilon))\\!=\\!\sigma(p_{i-1}(c))\\!=\\!\sigma(p_{i-1}(c+\varepsilon))$
and
$\sigma(p_{i+1}(c-\varepsilon))\\!=\\!\sigma(p_{i+1}(c))\\!=\\!\sigma(p_{i+1}(c+\varepsilon))$.
$\blacksquare$

## Acknowledgements

We are most grateful for Jerry Friesen’s constant support of this project.

## References

  * [BPR06] Basu, Saugata; Pollack, Richard; and Roy, Marie-Françoise, Algorithms in Real Algebraic Geometry, Algorithms and Computation in Mathematics, vol. 10, 2nd ed., Springer-Verlag, 2006\.
  * [Can88] Canny, John F., “Some Algebraic and Geometric Computations in PSPACE,” Proc. 20${}^{\text{\text@underline{th}}}$ ACM Symp. Theory of Computing, Chicago (1988), ACM Press.
  * [Stu35] Sturm, Jacques Charles-François, “Mémoire sur la résolution des équations numériques,” Inst. France Sc. Math. Phys., 6 (1835).


# Heralded Three-Photon Entanglement from a Single-Photon Source on a Photonic
Chip

Si Chen  Li-Chao Peng  Yong-Peng Guo  Xue-Mei Gu  Xing Ding  Run-Ze Liu  Hefei
National Research Center for Physical Sciences at the Microscale and School of
Physical Sciences, University of Science and Technology of China, Hefei
230026, China  Shanghai Research Center for Quantum Science and CAS Center for
Excellence in Quantum Information and Quantum Physics, University of Science
and Technology of China, Shanghai 201315, China  Hefei National Laboratory,
University of Science and Technology of China, Hefei 230088, China  Xiang You
Hefei National Research Center for Physical Sciences at the Microscale and
School of Physical Sciences, University of Science and Technology of China,
Hefei 230026, China  Shanghai Research Center for Quantum Science and CAS
Center for Excellence in Quantum Information and Quantum Physics, University
of Science and Technology of China, Shanghai 201315, China  Hefei National
Laboratory, University of Science and Technology of China, Hefei 230088, China
University of Science and Technology of China, School of Cyberspace Security,
Hefei, China  Jian Qin  Yun-Fei Wang  Yu-Ming He  Hefei National Research
Center for Physical Sciences at the Microscale and School of Physical
Sciences, University of Science and Technology of China, Hefei 230026, China
Shanghai Research Center for Quantum Science and CAS Center for Excellence in
Quantum Information and Quantum Physics, University of Science and Technology
of China, Shanghai 201315, China  Hefei National Laboratory, University of
Science and Technology of China, Hefei 230088, China  Jelmer J. Renema
Adaptive Quantum Optics Group, Mesa+ Institute for Nanotechnology, University
of Twente, P.O. Box 217, 7500 AE Enschede, Netherlands  Yong-Heng Huo  Hui
Wang  Chao-Yang Lu  Jian-Wei Pan  Hefei National Research Center for Physical
Sciences at the Microscale and School of Physical Sciences, University of
Science and Technology of China, Hefei 230026, China  Shanghai Research Center
for Quantum Science and CAS Center for Excellence in Quantum Information and
Quantum Physics, University of Science and Technology of China, Shanghai
201315, China  Hefei National Laboratory, University of Science and Technology
of China, Hefei 230088, China

###### Abstract

In the quest to build general-purpose photonic quantum computers, fusion-based
quantum computation has risen to prominence as a promising strategy. This
model allows a ballistic construction of large cluster states which are
universal for quantum computation, in a scalable and loss-tolerant way without
feed-forward, by fusing many small $n$-photon entangled resource states.
However, a key obstacle to this architecture lies in efficiently generating
the required essential resource states on photonic chips. One such critical
seed state that has not yet been achieved is the heralded three-photon
Greenberger-Horne-Zeilinger (3-GHZ) state. Here, we address this elementary
resource gap, by reporting the first experimental realization of a heralded
dual-rail encoded 3-GHZ state. Our implementation employs a low-loss and fully
programmable photonic chip that manipulates six indistinguishable single
photons of wavelengths in the telecommunication regime. Conditional on the
heralding detection, we obtain the desired 3-GHZ state with a fidelity
$0.573\pm 0.024$. Our work marks an important step for the future fault-
tolerant photonic quantum computing, leading to the acceleration of building a
large-scale optical quantum computer.

Photon is a favourable candidate for universal quantum computing [1, 2, 3],
allowing several advantages such as room-temperature operation, negligible
decoherence, and easy integration into existing fiber-optic-based
telecommunications systems. Especially, the rapidly developed integrated
optics makes it an appealing physical platform for large-scale fault-tolerant
quantum computing [4, 5, 6].

Measurement-based quantum computing (MBQC) [7, 8, 9, 10], where quantum
algorithms are performed by making single qubit measurements on a large
entangled state—usually called cluster states, holds significant potential for
photonic systems based on linear optics. Photonic cluster states can be
efficiently created from small resource states in a fusion mechanism [11, 12].
Later, a ballistic strategy for MBQC has been proposed [13, 14, 15], enabling
scalable and loss-tolerant generation of large cluster states by fusing many
small entangled resource states without any feed-forward, which has
subsequently renormalized to fusion-based quantum computation [16]. So far,
the heralded three-photon Greenberger-Horne-Zeilinger state has been
identified as the minimal initial entangled state [16], serving as an
essential building block for constructing large entangled cluster states [14,
17, 6].

Deterministic generations of multiphoton cluster states from single-photon
sources have been proposed [18, 19, 20] and implemented [21, 22, 23, 24].
However, high-quality deterministic preparation still remains challenging with
existing technology. Alternatively, without detecting or destroying the
photons, one can near-deterministically generate such entangled clusters with
heralded 3-GHZ states, which can be obtained using six single photons [25,
26].

Here, we report the first experimental demonstration of a heralded dual-
encoded 3-GHZ state using six single photons manipulated in a photonic chip. A
high-quality single-photon source based on a semiconductor quantum dot [27]
embedded in an open microcavity is used to deterministically produce single
photons that are converted to the telecommunication band with a quantum
frequency converter [28, 29]. These single photons are deterministically
demultiplexed into six indistinguishable single-photon sources [30, 31], which
are manipulated in a fully programmable photonic chip [32]. Heraled by the
detection of four output spatial modes with high-efficiency single-photon
detectors, we obtain a heralded 3-GHZ state with a fidelity of $0.573\pm
0.024$. Our work is an important step towards fault-tolerant scalable photonic
quantum computation.

Figure 1: The heralded generation scheme for a 3-GHZ state. Six single photons
are prepared at the input ports of a linear optical circuit, where we can
describe the initial input quantum state as
$\lvert{\psi_{in}}\rangle=\lvert{1011010110}\rangle$ with 0 and 1 being the
number of photons in each mode. The photonic circuit (depicted in the light
cyan background color), which contains twelve beams splitters of three
different transmissions 1/2 (black), 1/4 (blue), 2/3 (orange) and two $\pi$
phase shifters (purple), implements a required unitary transformation $U$ for
a 3-GHZ state. The 3-GHZ state in dual-rail encodings (a single photon
appearing in only one of the two spatial modes describes a qubit such as
$Q_{1}$, $Q_{2}$ and $Q_{3}$) is heralded in the modes (1-6) by a measurement
pattern in the last four modes (7-10). Three phase-tunable Mach-Zehnder
interferometers of phases $\varphi_{i}$ and $\theta_{i}$ ($i=1,2,3$) are used
to perform quantum state measurements on the created GHZ state.

Fig. 1 illustrates a heralded generation of a dual-rail-encoded 3-GHZ state
out of six single photons [26]. The scheme exploits a ten-mode linear optical
circuit, which consists of twelve optical beams plitters with three distinct
transmission coefficients and a pair of $\pi$-phase shifters. Six photons are
injected into six specific input modes of the photonic circuit, preparing a
number-basis initial state represented as
$\lvert{\psi_{in}}\rangle=a_{1}^{\dagger}a_{3}^{\dagger}a_{4}^{\dagger}a_{6}^{\dagger}a_{8}^{\dagger}a_{9}^{\dagger}\lvert{0}\rangle^{\otimes
10}=\lvert{1011010110}\rangle$. Here, $a_{i}^{\dagger}$ refers to the creation
operator in mode $i$, $\lvert{0}\rangle$ symbolizes the vacuum state, and the
numbers $0$ and $1$ indicate the number of photons occupied in each mode. The
underlying unitary transformation $U$ of the circuit is optimally
parameterized such that a particular measurement patterns in four ancillary
modes (7-10) herald a desired 3-GHZ state at six output modes (1-6) [26].
Qubits $Q_{1}$, $Q_{2}$ and $Q_{3}$ are identified with output mode pairs
(1,2), (3,4) and (5,6). This association uses a dual-rail encoding method,
which signifies the presence of one single photon in either of the two spatial
modes within each mode pair, e.g., $\lvert{0}\rangle_{d}=\lvert{10}\rangle$
and $\lvert{1}\rangle_{d}=\lvert{01}\rangle$. The GHZ state is heralded in
modes (1-6) only when single photons are detected in both (7,8) and in just
one of the (9,10) ports, with the other one remaining in a vacuum state. Each
event has a success probability of $1/108$, resulting in an overall success
rate of $1/54$ [26]. Using a phase-tunable Mach-Zehnder interferometers (MZIs)
at each output mode pair, one can perform arbitrary local projective
measurements for estimating the full state. Details of the underlying state
evolution and state measurements are provided in Supplementary.

To prepare six single photons, we firstly use the state-of-the-art self-
assembled InAs/GaAs quantum dot (QD), which is coupled to an polarized and
tunable microcavity [33, 34] and cooled down to $\sim$4 K. Under resonant
pumping by a $\pi$-pulse laser with a repetition rate of $\sim$76 MHz, the QD
emits $\sim$50 MHz polarized resonance fluorescence single photons at the end
of the single-mode fiber. We measured second-order correlation of the photon
source with a Hanbury Brown-Twiss (HBT) interferometer [35], and obtained
$g^{2}(0)=0.028(8)$ at zero delay, which indicates a high single-photon purity
of 97.2(8)%. The single photon indistinguishability is tested using a Hong-Ou-
Mandel (HOM) interferometer [36], yielding a visibility of 89(1)% between two
photons separated by $\sim$13 ns.

We then employ a quantum frequency converter (QFC) to transfer the near-
infrared wavelength of the produced single photons to the preferable
telecommunication regime [29]. For this purpose, we fabricate a periodically
poled lithium niobate (PPLN) waveguide for difference-frequency generation
process that can be adjusted by the wavelengths of the pump lasers. A
continuous wave (CW) pump laser at $\sim$2060 nm and the QD-emitted single
photons at $\sim$884.5 nm are then coupled into the PPLN waveguide, in which
the difference frequency generation occurs, thus generating the output single
photons at 1550 nm. By optimizing the waveguide coupling, and transmission and
detection rate, we eventually achieve a overall single-photon conversion
efficiency of $\sim$50%. To test whether the converted photons still preserve
the single-photon nature and their indistinguishability, we preform the HBT
and HOM measurements on the photons after conversion. The purity of the single
photons at 1550 nm stays $97.4(6)\%$, and the indistinguishability between
photon 1 and photons 2, 3, 4, 5, 6 are respectively 0.883(7), 0.86(1),
0.86(3), 0.88(1), 0.87(3), as shown in Fig. 3 (a) and (b).

Figure 2: The experimental setup. A single InAs/GaAs quantum dot, resonantly
coupled to an open microcavity, is used to produce pulsed resonance
fluorescence single photons. The wavelength of these single photons in near-
infrared is then converted into telecom-wavelength of 1550 nm with a quantum
frequency converter by coupling a continuous wave laser and single photons
into a periodically poled lithium niobate waveguide. Five pairs of Pockels
cells and polarizing beam splitters are employed to actively translate a
stream of single photons into six spatial modes. Optical fibers of different
lengths are used to precisely compensate time delays. The six
indistinguishable single photons are then fed into a 12-modes programmable
linear-optical quantum circuit, which allows the preparation and measurement
of a heralded three-qubit dual-rail encoded GHZ state. The single photons at
the output ports of the photonic circuit is detected by superconducting
nanowire single-photon detectors. All coincidence are recorded by a
coincidence count unit (not shown).

The converted single-photon stream is then deterministically demultiplexed
into six spatial modes using a tree-like structure demultiplexer constructed
by five pairs of Pockels cells (PCs) and polarizing beam splitters (PBSs). The
PCs, synchronized to the laser pulses and operated at a repetition rate of
$\sim$705 kHz, actively control the photon polarization when loaded with high-
voltage electrical pulses. The measured average optical switches efficiency is
$\sim$77%, which is mainly due to the coupling efficiency and propagation
loss. With the help of six single-mode fibers of different lengths and
translation stages, we precisely compensate the relative time delays of the
six single photons such that they can simultaneously arrive at the input ports
of the photonic circuit.

To realize the functional design of the unitary transformation in Fig. 1, we
employ a photonic chip that is low-loss and fully programmable [32]. The
circuit is based on stoichiometric silicon nitride waveguides which are
fabricated for single-mode operation at a wavelength of 1550 nm. It consists
12 input and output spatial modes that are interconnected through an
arrangement of adjustable beam splitters and thermo-optic phase shifters, as
shown in Fig.2 (details about the photonic circuit, please refer to Ref.
[32]). To achieve a heralded 3-GHZ state, six single photons are injected into
six inputs (1, 3, 4, 6, 8, 9) of the circuit and propagate through the
circuit. The heralded outputs are 7, 8, 9 and 10. At each heralded output (7,
8, 9), two superconducting nanowire single-photon detectors (SNSPDs) are
employed and act as a pseudo-photon-number-detector that can resolve up to two
photons. When each mode (7, 8, 9) contains a single photon and mode 10 has
vacuum state, one can obtain a heralded GHZ generation for three dual-rail
encoded qubits defined in the modes $Q1=(1,2)$, $Q2=(3,4)$ and $Q3=(5,6)$.

Figure 3: Characterization of the single-photon source and the photonic
quantum circuit. (a), The purity of the single-photon source of telecom-
wavelength is evaluated by a second-order correlation function $g^{2}(0)$. The
observed anti-bunched peak at zero-time delay reveals $g^{2}(0)=0.026(6)$.
(b), Measurement of the photon indistinguishability by performing a Hong-Ou-
Mandel interferometer between photon 1 and photon 2 (3, 4, 5 or 6). The
corresponding measured indistinguishability are $0.883(7)$, $0.86(1)$,
$0.86(3)$, $0.88(1)$, $0.87(3)$, respectively. The error bars indicates one
standard deviation, deduced from propagated Poissonian counting statistics of
the raw photon detection events. (c)-(d), Amplitude (c) and Phase (d) of the
ideal unitary transformation matrix (black wire frames) and their
experimentally reconstructions (colored bars). We send six single photons into
the used six input ports of the photonic circuit, and measure the normalized
amplitude and phase for each input–output combination.

We then send the six photons one by one and measure the output distribution at
the nine output modes (1-9) for analyzing the quality of the photonic circuit.
For each input-output combination, we implement a Mach-Zehnder-type coherence
measurement to record the corresponding phase. The normalized amplitude and
measured phase compared to their theoretical distributions are summarized in
Fig. 3 (c) and (d).

To analyze the generated heralded three-photon GHZ state in dual-rail
encoding, we use the phase-tunable MZIs to perform any local projective
measurements on the single photons. The transformation matrixes of these local
measurements are compiled in the whole circuit. We then collect the six-photon
coincidence counts at the used ten outputs in which each output mode (7, 8, 9)
contains only one photon. To validate the three-qubit GHZ entanglement, we
first measure the six-photon events in the
$\lvert{0}\rangle_{d}/\lvert{1}\rangle_{d}$ basis (see data in Fig. 4 (a)) to
calculate the population of
$(\lvert{0}\rangle_{d}\langle{0}\rvert_{d})^{\otimes
3}+(\lvert{1}\rangle_{d}\langle{1}\rvert_{d})^{\otimes 3}$ over all the
possible $2^{3}$ combinations, leading to a population $P=0.758\pm 0.025$. We
further estimate the expectation value of the observable $M^{\bigotimes
N}_{\theta}=(\cos\theta\hat{\sigma}_{x}+\sin\theta\hat{\sigma}_{y})^{\bigotimes
N}$, where $\theta=k\pi/3$ ($k=0,1,2$) and
$\hat{\sigma}_{x}$,$\hat{\sigma}_{y}$ are Pauli matrices. The coherence of the
three-qubit GHZ state is defined by the off-diagonal element of its density
matrix and can be calculated by $C=(1/3)\sum_{k=0}^{2}(-1)^{k}\langle
M_{k\pi/3}^{\bigotimes 3}\rangle$, which is $C=0.389\pm 0.040$ (see data in
Fig. 4 (b)). The state fidelity can be directly estimated by
$F=(P+C)/2=0.573\pm 0.024$, which surpasses the classical threshold of 0.5 by
more than 3 standard deviations and is sufficient to show the presence of
entanglement [37].

Figure 4: Experimental results of the generated heralded three-qubit GHZ
state. (a), Six-photon coincidence counts measured in the dual-rail basis
$\lvert{0}\rangle_{d}/\lvert{1}\rangle_{d}$ accumulated for 23 h. (b),
Expectation values of $\langle M^{\otimes 3}_{\theta}\rangle$ with phase shift
being $\theta=k\pi/3$ ($k=0,1,2$), each obtained from the measurement in the
basis of $(\lvert{0}\rangle_{d}\pm e^{i\theta}\lvert{1}\rangle_{d})/\sqrt{2}$.
Error bars indicate one standard deviation calculated from Poissonian counting
statistics of the raw detection events.

In summary, we have demonstrated, for the first time, the heralded three-
photon GHZ state using six photons from a high-quality quantum-dot single-
photon source and a 12-mode fully programmable photonic chip. It should be
noted that this experiment is unrealistic for commonly used spontaneous
parametric down-conversion sources [38], since the expected count rate will be
four orders of magnitude smaller than this experiment, showing a huge
advantage of deterministic quantum-dot single-photon sources. Our demonstrated
three-qubit GHZ state is heralded and has a heralding efficiency that could
reach to one in principle, which is the main building block for fusion-based
photonic quantum computing. Here, the heralding efficiency is defined as the
probability of successfully achieving a desired GHZ state when there are
coincidences of desired heralding detectors. In our experiment, we obtain a
heralding efficiency of $\sim$0.0005 after the correction of detectors’
imperfections (see Supplementary). This heralding efficiency can be
significantly improved in the near future, by further promoting the efficiency
of single-photon sources and photonic circuit to enable the large-scale
photonic quantum computing.

S. C. and L.-C P. contributed equally to this work.

## References

  * Knill  _et al._ [2001] E. Knill, R. Laflamme, and G. J. Milburn, Nature 409, 46 (2001).
  * Kok  _et al._ [2007] P. Kok, W. J. Munro, K. Nemoto, T. C. Ralph, J. P. Dowling, and G. J. Milburn, Reviews of Modern Physics 79, 135 (2007).
  * Pan  _et al._ [2012] J.-W. Pan, Z.-B. Chen, C.-Y. Lu, H. Weinfurter, A. Zeilinger, and M. Żukowski, Reviews of Modern Physics 84, 777 (2012).
  * O’brien [2007] J. L. O’brien, Science 318, 1567 (2007).
  * Ladd  _et al._ [2010] T. D. Ladd, F. Jelezko, R. Laflamme, Y. Nakamura, C. Monroe, and J. L. O’Brien, Nature 464, 45 (2010).
  * Rudolph [2017] T. Rudolph, APL Photonics 2, 030901 (2017).
  * Raussendorf and Briegel [2001] R. Raussendorf and H. J. Briegel, Phys. Rev. Lett. 86, 5188 (2001).
  * Raussendorf  _et al._ [2003] R. Raussendorf, D. E. Browne, and H. J. Briegel, Phys. Rev. A 68, 022312 (2003).
  * Walther  _et al._ [2005] P. Walther, K. J. Resch, T. Rudolph, E. Schenck, H. Weinfurter, V. Vedral, M. Aspelmeyer, and A. Zeilinger, Nature 434, 169 (2005).
  * Briegel  _et al._ [2009] H. J. Briegel, D. E. Browne, W. Dür, R. Raussendorf, and M. Van den Nest, Nature Physics 5, 19 (2009).
  * Browne and Rudolph [2005] D. E. Browne and T. Rudolph, Phys. Rev. Lett. 95, 010501 (2005).
  * Duan and Raussendorf [2005] L.-M. Duan and R. Raussendorf, Phys. Rev. Lett. 95, 080503 (2005).
  * Kieling  _et al._ [2007] K. Kieling, T. Rudolph, and J. Eisert, Phys. Rev. Lett. 99, 130501 (2007).
  * Gimeno-Segovia  _et al._ [2015] M. Gimeno-Segovia, P. Shadbolt, D. E. Browne, and T. Rudolph, Phys. Rev. Lett. 115, 020502 (2015).
  * Pant  _et al._ [2019] M. Pant, D. Towsley, D. Englund, and S. Guha, Nature Communications 10, 1070 (2019).
  * Bartolucci  _et al._ [2023] S. Bartolucci, P. Birchall, H. Bombin, H. Cable, C. Dawson, M. Gimeno-Segovia, E. Johnston, K. Kieling, N. Nickerson, M. Pant, _et al._ , Nature Communications 14, 912 (2023).
  * Zaidi  _et al._ [2015] H. A. Zaidi, C. Dawson, P. van Loock, and T. Rudolph, Phys. Rev. A 91, 042301 (2015).
  * Lindner and Rudolph [2009] N. H. Lindner and T. Rudolph, Phys. Rev. Lett. 103, 113602 (2009).
  * Economou  _et al._ [2010] S. E. Economou, N. Lindner, and T. Rudolph, Phys. Rev. Lett. 105, 093601 (2010).
  * Gimeno-Segovia  _et al._ [2019] M. Gimeno-Segovia, T. Rudolph, and S. E. Economou, Phys. Rev. Lett. 123, 070501 (2019).
  * Schwartz  _et al._ [2016] I. Schwartz, D. Cogan, E. R. Schmidgall, Y. Don, L. Gantz, O. Kenneth, N. H. Lindner, and D. Gershoni, Science 354, 434 (2016).
  * Lee  _et al._ [2019] J. Lee, B. Villa, A. Bennett, R. Stevenson, D. Ellis, I. Farrer, D. Ritchie, and A. Shields, Quantum Science and Technology 4, 025011 (2019).
  * Thomas  _et al._ [2022] P. Thomas, L. Ruscio, O. Morin, and G. Rempe, Nature 608, 677 (2022).
  * Cogan  _et al._ [2023] D. Cogan, Z.-E. Su, O. Kenneth, and D. Gershoni, Nature Photonics 17, 324 (2023).
  * Varnava  _et al._ [2008] M. Varnava, D. E. Browne, and T. Rudolph, Phys. Rev. Lett. 100, 060502 (2008).
  * Gubarev  _et al._ [2020] F. V. Gubarev, I. V. Dyakonov, M. Y. Saygin, G. I. Struchalin, S. S. Straupe, and S. P. Kulik, Phys. Rev. A 102, 012604 (2020).
  * Senellart  _et al._ [2017] P. Senellart, G. Solomon, and A. White, Nature Nanotechnology 12, 1026 (2017).
  * Weber  _et al._ [2019] J. H. Weber, B. Kambs, J. Kettler, S. Kern, J. Maisch, H. Vural, M. Jetter, S. L. Portalupi, C. Becher, and P. Michler, Nature Nanotechnology 14, 23 (2019).
  * You  _et al._ [2022] X. You, M.-Y. Zheng, S. Chen, R.-Z. Liu, J. Qin, M.-C. Xu, Z.-X. Ge, T.-H. Chung, Y.-K. Qiao, Y.-F. Jiang, _et al._ , Advanced Photonics 4, 066003 (2022).
  * Wang  _et al._ [2017] H. Wang, Y. He, Y.-H. Li, Z.-E. Su, B. Li, H.-L. Huang, X. Ding, M.-C. Chen, C. Liu, J. Qin, _et al._ , Nature Photonics 11, 361 (2017).
  * Wang  _et al._ [2019a] H. Wang, J. Qin, X. Ding, M.-C. Chen, S. Chen, X. You, Y.-M. He, X. Jiang, L. You, Z. Wang, _et al._ , Phys. Rev. Lett. 123, 250503 (2019a).
  * Taballione  _et al._ [2021] C. Taballione, R. van der Meer, H. J. Snijders, P. Hooijschuur, J. P. Epping, M. de Goede, B. Kassenberg, P. Venderbosch, C. Toebes, H. van den Vlekkert, _et al._ , Materials for Quantum Technology 1, 035002 (2021).
  * Wang  _et al._ [2019b] H. Wang, Y.-M. He, T.-H. Chung, H. Hu, Y. Yu, S. Chen, X. Ding, M.-C. Chen, J. Qin, X. Yang, _et al._ , Nature Photonics 13, 770 (2019b).
  * Tomm  _et al._ [2021] N. Tomm, A. Javadi, N. O. Antoniadis, D. Najer, M. C. Löbl, A. R. Korsch, R. Schott, S. R. Valentin, A. D. Wieck, A. Ludwig, _et al._ , Nature Nanotechnology 16, 399 (2021).
  * Hanbury Brown and Twiss [1956] R. Hanbury Brown and R. Twiss, Nature 178, 1447 (1956).
  * Hong  _et al._ [1987] C. K. Hong, Z. Y. Ou, and L. Mandel, Phys. Rev. Lett. 59, 2044 (1987).
  * Gühne and Tóth [2009] O. Gühne and G. Tóth, Physics Reports 474, 1 (2009).
  * Zhong  _et al._ [2018] H.-S. Zhong, Y. Li, W. Li, L.-C. Peng, Z.-E. Su, Y. Hu, Y.-M. He, X. Ding, W. Zhang, H. Li, _et al._ , Phys. Rev. Lett. 121, 250505 (2018).