[datatype=bibtex, overwrite] [fieldset=address, null] [fieldset=location,
null]

# Counting cherry reduction sequences is counting linear extensions (in
phylogenetic tree-child networks)

Tomás M. Coronadoa,1, Joan Carles Ponsa,1, Gabriel Rieraa,1,*
a Department of Mathematics and Computer Science,
Universitat de les Illes Balears, Spain
1 All authors have contributed equally
* Corresponding author<EMAIL_ADDRESS>
(March 2024)

## Abstract

Orchard and tree-child networks share an important property with phylogenetic
trees: they can be completely reduced to a single node by iteratively deleting
cherries and reticulated cherries. As it is the case with phylogenetic trees,
the number of ways in which this can be done gives information about the
topology of the network. Here, we show that the problem of computing this
number in tree-child networks is akin to that of finding the number of linear
extensions of the poset induced by each network, and give an algorithm based
on this reduction whose complexity is bounded in terms of the level of the
network.

##  1 Introduction

Phylogenetics is the discipline concerned with the study of the evolutionary
relationships among taxa that are supposed to evolve in a temporal series of
contingent events [2], mainly organisms, genes and languages. The primary goal
is to understand and reconstruct those relationships, elucidating the
evolutionary patterns that have led to their current diversity.

Most of the fundamental goals of phylogenetics can be formulated in
mathematical language and as mathematical and computational problems to be
solved. In fact, ever since the time of Lamarck and Darwin, the representation
of evolution itself has been historically done in terms of graphs.
Traditionally, these graphs have been rooted trees; that is: (directed) rooted
acyclic graphs, without nodes allowing multiple incoming edges. The
distinguished node (the root) corresponds to the most recent common ancestor
of the taxa under consideration; the leaves represent extant taxa, and
interior nodes represent (only) speciation events.

However, the evolutionary history of organisms is often more complex than a
simple tree-like structure. Reticulate events, such as hybridization,
horizontal gene transfer, and recombination, are better represented in
networks rather than in trees. Phylogenetic networks generalize phylogenetic
trees allowing the possibility for nodes to have multiple (in the binary
setting, exactly two) incoming edges. Those nodes represent the reticulation
events; see Subsection 2.3 for formal definitions.

A particularity of (binary) phylogenetic trees is that they can all be
generated by means of iteratively adding cherries (pairs of leaves; see
Subsection 2.4 for a formal definition) to a tree with only one leaf [24, p.
28]; but this is tantamount to saying that any particular tree can be
recursively reduced to a single leaf. These reductions have an evolutionary
meaning, since they are used to distill or simplify the evolutionary
information contained in a phylogenetic tree into a more manageable form.
However, it is not possible, given a general phylogenetic network, to reduce
it to a single node. In 2019, a new class of phylogenetic networks was
introduced whose aim was to mimic precisely this property: the class of
orchard, or cherry-picking, phylogenetic networks [11, 16]. Roughly speaking,
these are defined as phylogenetic networks that can be reduced to a single
leaf by an iterative process of reductions consisting in (1) simplifying a
cherry, or (2) simplifying a reticulated cherry; see Subsection 2.4 for formal
definitions. Orchard networks were initially introduced for their
computational benefits: for instance, providing a polynomial-time algorithm
for their reconstruction from its “ancestral profile” in [11], or providing a
linear-time algorithm for the Network Containment problem — a generalization
of the Tree Containment problem — for inputs of tree-child networks (a
subclass of orchard networks), which is NP-complete for general phylogenetic
networks, in [16]. Moreover, orchard networks are integrated in the set of
biologically relevant phylogenetic networks (according to [15] and [19]).

For any given orchard network, there may be multiple ways of reducing an
orchard network to a single leaf, and this number gives information about the
topology of the network. In [11] the question about the feasibility of
counting the number of these reductions (called cherry reduction sequences)
was posed. In this paper, we study this question in the context of tree-child
networks [6], which are a subclass of orchard networks, in fact one of the
most popular classes of phylogenetic networks. They are extensively studied
both for their mathematical and their computational applications; see [26, 3,
25], to name a few.

In this paper, we study this problem by reducing it to that of counting linear
extensions [18]. Given a poset $(X,\preceq)$, a linear extension is a
bijection $\pi:\\{1,\ldots,|X|\\}\to X$ such that $x\preceq y$ implies
$\pi^{-1}(x)\leqslant\pi^{-1}(y)$; i.e., a total order $\leqslant$ that is
compatible with $\preceq$. Then, an algorithm is proposed whose complexity is
studied in terms of the level of the input tree-child network.

The paper is organized as follows. First, we provide some needed background
and notation from graph theory, phylogenetics and combinatorics in Section 2.
Section 3 contains the main theoretical result of this paper, which is then
used at the start of Section 4 to provide an algorithm built on top of the
work of [18]. In the same section, upper and lower bounds of the complexity of
our algorithm relating the tree-width parameter and the level of a
phylogenetic network are discussed in the context of determining the
complexity of the algorithm without having to study its tree-width. The paper
ends with a Conclusions section.

##  2 Preliminaries

###  2.1 Graph theory

In this paper we will need some graph theory definitions that are not always
used in the study of phylogenetic networks. Hence, we have opted to present
them here in an independent fashion. First of all, for a directed or
undirected graph $G$ we denote its sets of nodes and edges by $V(N)$ and
$E(N)$, respectively, and for any directed graph $G$, we shall denote its
underlying (undirected) graph by $U(G)$. In order to ease the proofs, we will
not allow the existence of loops (that is, edges that begin and end in the
same node).

A subgraph of an undirected graph is _biconnected_ when it is connected and it
remains connected after removing any node from it and all arcs incident to
that node. A subgraph of a directed graph $G$ is _biconnected_ when it is so
in $U(G)$.

Given a directed graph $G$, we say that it is _weakly connected_ if its
underlying graph, $U(G)$, is connected. If $U(G)$ is not connected, then each
of the connected components of $U(G)$ is a _weakly connected component_ of
$G$. In the same fashion, we say that a directed subgraph is _strongly
connected_ if it is connected as a directed graph; moreover, a _strong path_
is a path connecting one to the other as a directed graph.

Let $G$ be a graph and $e=uv$ an edge, for some $u,v\in V(G)$. The
_contraction_ of $e$ in $G$, denoted by $G/_{{\displaystyle\\!e}}$, is the
result of subtracting $e$ and identifying $u$ and $v$ in a node $w$ that
inherits all the adjacencies of both $u$ and $v$. Formally,
$G/_{{\displaystyle\\!e}}$ is the _quotient_ $G/_{{\displaystyle\\!\sim}}$,
where $\sim$ identifies $u$ and $v$ but leaves every other node alone (and
then, since we do not allow loops, we remove the edge between $[u]$ and
$[v]$). When applying any edge contraction to a directed graph, we always
assume the result to be undirected, as it may produce conflicting edge
directions.

A _minor_ of an undirected graph $G$ is the result of repeatedly applying the
process of contraction to a subgraph of $G$ [8]. In what follows, we shall
view minors as quotients of these subgraphs, and therefore each of their nodes
as an equivalence class. Notice that the nodes in each of these classes form a
connected subgraph of $G$. We shall often refer to a minor of a directed
graph, in which case we are refering to a minor of its underlying graph.

We denote the _tree-width_ [8] of a graph $G$ by $\mathrm{tw}(G)$; and if $G$
is a directed graph, $\mathrm{tw}(G)$ will denote the tree-width of its
underlying graph $U(G)$. A precise definition of the tree-width of a graph can
be found in [8], but to our purposes it suffices to know that if $H$ is a
minor of $G$, then $\mathrm{tw}(H)\leqslant\mathrm{tw}(G)$ (Lemma 12.4.1 in
[8]) and that the tree-width of a clique $K_{n}$ is $n-1$ [23].

###  2.2 Partial orders and reachability

For any set, a _partial order_ over it is a relation $\preceq$ that is
reflexive, antisymmetric and transitive. A set $X$ with such a relation is
called a _partially ordered set_ , or _poset_ and given as $(X,\preceq)$
(although we often omit this and write $X$). If there exists $x\in X$ such
that there is no $y\in X\setminus\\{x\\}$ such that $y\preceq x$, we say that
$x$ is _minimal_. Analogously, if there exists $x\in X$ such that there is no
$y\in X\setminus\\{x\\}$ and $x\preceq y$, we say that $x$ is _maximal_.

Given a poset $(X,\preceq)$ and $x,y\in X$, if $x\neq y$ and $x\preceq y$ then
$x\prec y$. Moreover, we say that $y$ _covers_ $x$ and denote it by
$x\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}y$ if $x\prec y$ and there exists
no other element $z\in X$ such that $x\prec z\prec y$. For any poset $X$, its
_cover graph_ (sometimes referred to as _Hasse diagram_) is a directed graph
whose set of nodes is $X$ and its set of edges is $\\{xy\in X\times
X:x\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}y\\}$. We denote the cover graph
of $X$ as $\mathcal{C}(X)$.

Given any poset $X$, we can define its _order-dual_ poset $(X,\succeq)$, also
denoted by $X^{\mathrm{op}}$, which is a poset with the same underlying set
endowed with a relation $\succ$ defined by the rule $x\succeq y$ if, and only
if, $y\preceq x$ for all $x,y\in X$.

A _linear extension_ of a poset $(X,\preceq)$ is a bijection
$\pi:\\{1,\ldots,|X|\\}\to X$ such that for all $x,y\in X$, $x\preceq y$
implies $\pi^{-1}(x)\leqslant\pi^{-1}(y)$. The set of all linear extensions of
$X$ is denoted by $\mathrm{LinExt}(X)$.

For any directed acyclic graph $N$ (henceforth, a DAG), any subset $X\subseteq
V(N)$ is endowed with a partial order by the structure of the graph as
follows: a node $v$ is said to be _reachable from $u$_ if there exists a path
$u\leadsto v$ within $N$. Then relation of reachability ($\leadsto$) induces a
partial order over any subset $X\subseteq V(N)$: for any $u,v\in V(N)$,
$u\preceq v$ if, and only if, $u\leadsto v$.

###  2.3 Phylogenetic networks

Let $\Sigma$ be a finite set of labels. By a _phylogenetic network_ on
$\Sigma$ we understand a rooted directed acyclic graph (rDAG) where each node
of in-degree $\geqslant 2$ has out-degree exactly 1 and whose _leaves_ (i.e.,
its nodes of out-degree 0) are bijectively labeled in $\Sigma$ [14]. A
_phylogenetic tree_ is simply a phylogenetic network without nodes of in-
degree $\geqslant 2$. The definition of phylogenetic tree and network also
forbids, for reconstructibility reasons, the existence of _elementary nodes_ ,
that is, of nodes of in-degree and out-degree both equal to 1.

Let $N$ be a phylogenetic network on $\Sigma$. We shall denote its _root_
(i.e., its only node of in-degree 0) by $\rho$ and we shall always identify
its leaves with their corresponding labels. Given two nodes $u,v$ in $N$, we
say that $v$ is a _child_ of $u$, and also that $u$ is a _parent_ of $v$, when
$uv\in E(N)$. A node in $N$ is of _tree type_ , or a _tree node_ , when its
in-degree is $\leqslant 1$ (thus including the root), and a _reticulation_
when its in-degree is $\geqslant 2$ (and hence, its out-degree is 1). For any
rDAG $N$, we define $T(N)$ as the set of tree nodes of $N$, i.e., the set of
nodes of $N$ with in-degree at most $1$; conversely, we denote by $R(N)$ the
set of its reticulation nodes.

In the context of phylogenetic networks, maximal biconnected components are
often referred to as _blobs_. Moreover, every blob of a phylogenetic network
has one, and only one, node that is ancestor of all nodes in the blob. The
_level_ of a phylogenetic network is the maximum number of reticulations among
its blobs. Notice that each blob has at least one reticulation. A level-$k$
network is then a phylogenetic network where each of its blobs has at least
$k$ reticulations.

A phylogenetic network is _tree-child_ [7] if all its internal nodes (i.e. its
nodes of out-degree $\geqslant 1$) have at least one child of tree type. In
this paper, we restrict ourselves to _binary_ phylogenetic networks — this is,
networks where all internal nodes except for the root have either in-degree 1
and out-degree 2 or in-degree 2 and out-degree 1. The root will always have
in-degree 0, and out-degree 2 if it is not itself a leaf. We denote that a
rDAG $N$ has only one node (i.e. the root is a leaf) by $N\cong\star$.

###  2.4 Orchard networks and cherry reductions

Given a phylogenetic network $N$, we denote by $\mathring{N}$ the rDAG
obtained from $N$ by removing all its leaves and the edges incident to them.
If $N\cong\star$, then $\mathring{N}=\emptyset$ (as the root has out-degree
$0$).

Let $N$ be a phylogenetic network. A _cherry_ of $N$ is a subgraph of $N$
comprised of two leaves and their parent node. Analogously, _reticulated
cherry_ of $N$ is a subgraph of $N$ formed by two leaves, a reticulation node
and an internal tree node in such a way that the reticulation node is the
parent of one of those leaves and the child of the internal tree node, which
is in turn the parent of the other leaf (see Figure 1). A tree node is
_terminal_ if it is the root of a cherry or a reticulated cherry.

Let $N$ be a phylogenetic network and $u\in T(\mathring{N})$ be a terminal
node. The _cherry reduction_ rooted on $u$, denoted by $\mathrm{CR}(N,u)$, is
the network resulting of removing all the descendant edges and strict
descendant tree nodes of $u$ from $N$. We emphasize that we only remove all
the strict descendant _tree_ nodes of $u$. As we can see in Figure 1, the
reticulation in the right-side image is not removed, but becomes a new leaf
instead. Notice that $\mathrm{CR}(N,u)$ is a subnetwork of $N$ in the sense
that all the nodes and edges in $\mathrm{CR}(N,u)$ are nodes and edges of $N$.

An _orchard network_ [11] is a network $N$ that can be completely reduced by
the repeated application of cherry reductions; i.e., such that there exists a
sequence of subnetworks of $N$, namely $(N_{0},\,N_{1},\,\ldots,\,N_{s})$ such
that $N_{0}=N$, each $N_{i+1}$ is the result of a cherry reduction applied to
$N_{i}$, and $N_{s}\cong\star$. Notice that any two sequences of cherry
reductions of a given orchard network have the same length. We will denote the
set of all such sequences of cherry reductions of a given network $N$ by
$\mathrm{CR\text{-}Seq}(N)$. It will be important to remember that all tree-
child networks are orchard networks [11].

$\vdots$$u$$\vdots$$\cdots$$u$ Figure 1: The two different cherry reductions:
a regular cherry (left) and a reticulated cherry (right).

##  3 Cherry reductions and linear extensions

The aim of this section is to prove that there are as many cherry reduction
sequences as there are linear extensions of the poset of internal tree nodes
induced by a tree-child network (Theorem 5). We shall begin by showing how the
set of internal tree nodes is changed each time a cherry-reduction is
performed.

######  Lemma 1.

Let $N$ be an orchard network, $u\in T(\mathring{N})$ a terminal node, and
$N^{\prime}=\mathrm{CR}(N,u)$. Then
$T(\mathring{N})=T(\mathring{N}^{\prime})\sqcup\\{u\\}$ and $u\in
L(N^{\prime})$.

###### Proof.

That $u\in L(N^{\prime})$ springs from the fact that $N^{\prime}$ is obtained
from $N$ by removing all strict descendants of $u$ from $N$; thus,
$\mathrm{deg}_{\mathrm{out}}^{N^{\prime}}(u)=0$, and this is the definition of
a leaf. Therefore, $u\notin\mathring{N}^{\prime}$.

On the other hand, $u\in T(\mathring{N})$, by definition of $\mathrm{CR}$. ∎

######  Remark 1.

In particular, $\mathrm{CR}(N,-)$ is injective.

Remember that, for any set $X$, $\mathfrak{S}_{X}$ represents the set of
permutations of $X$, i.e. bijective functions $\\{1,\ldots,|X|\\}\to X$.

######  Lemma 2.

Let $N$ be an orchard network. The assignment

$\sigma:\mathrm{CR\text{-}Seq}(N)\to\mathfrak{S}$

that maps each $\mathrm{CR}$-sequence $(N_{0},\ldots,N_{s})$ of $N$ to the
permutation $(u_{0}\;\cdots\;u_{s-1})$, where
$N_{i+1}=\mathrm{CR}(N_{i},u_{i})$, is well-defined and injective.

###### Proof.

For the first part we need to prove that this construction yields a
permutation of $T(\mathring{N})$. Let $(N_{0},\ldots,N_{s})$ be a
$\mathrm{CR}$-sequence and $u_{0},\ldots,u_{s-1}$ the nodes such that
$N_{i+1}=\mathrm{CR}(N_{i},u_{i})$. By Lemma 1, these are uniquely determined
by $(N_{0},\ldots,N_{s})$. In addition, since $T(\mathring{N})\supseteq
T(\mathring{N}_{1})\supseteq\cdots\supseteq T(\mathring{N}_{s})$ and each
$u_{i}\in T(\mathring{N}_{i})$, we have $u_{i}\in T(\mathring{N})$. These are
also necessarily different from each other as $u_{i}\in
T(\mathring{N}_{i})\setminus T(\mathring{N}_{i+1})$. Since $\lvert
T(\mathring{N})\rvert=s$, it follows that $(u_{0}\;\cdots\;u_{s-1})$ is indeed
a permutation of $T(\mathring{N})$.

Finally, we must verify that $\sigma$ is injective. Let
$S=(N_{0},\ldots,N_{s})$ and
$S^{\prime}=(N_{0}^{\prime},\ldots,N_{s}^{\prime})$ be two
$\mathrm{CR}$-sequences for $N$. Note that both sequences must have the same
length, $\lvert T(\mathring{N})\rvert$. Assume that $\sigma(S)=(u_{0}\;\cdots
u_{s-1})=\sigma(S^{\prime})$. Then $N=N_{0}=N_{0}^{\prime}$ and at each step
we have $N_{i+1}=\mathrm{CR}(N_{i},u_{i})=N_{i+1}^{\prime}$, which provides
the proof by induction. ∎

The next lemma provides a useful and succinct relationship between the
terminal nodes in $T(\mathring{N})$ and the maximal nodes in its associated
poset if $N$ is a tree-child network.

######  Lemma 3.

For any tree-child network $N$, for any $u\in T(\mathring{N})$, $u$ is
terminal if, and only if, $u$ is maximal in $T(\mathring{N})$.

###### Proof.

If $u$ is terminal, then either it is the root of a cherry or that of a
reticulated cherry. In both cases, it does not have any strict descendant that
is internal tree node, and so it is maximal in $T(\mathring{N})$.

On the other hand, if $u$ is maximal in $T(\mathring{N})$, then it has no
strict descendant node that is both internal and a tree node. But since $N$ is
a tree-child network, at least one of its two children must be a leaf. Two
cases arise: if the other child is also a leaf, then it is the root of a
cherry. If the other child is a reticulation, then by the maximality of $u$
among internal tree nodes and the fact that $N$ is tree-child, the only child
of this reticulation must be a leaf. In either case, $u$ is a terminal node. ∎

######  Remark 2.

Lemma 3 is actually false for general orchard networks. Indeed, consider the
following example:

$u_{1}$$u_{2}$$u_{5}$$u_{4}$$u_{3}$$h_{1}$$h_{2}$

This network is obviously orchard: $(u_{3}\ u_{5}\ u_{4}\ u_{2}\ u_{1})$ gives
a cherry reduction sequence. However, even though $u_{4}$ is a maximal
internal tree node, there is no cherry reduction sequence that begins by it.

This same example negates the validity of the statement of Theorem 5 below for
general orchard networks.

In what follows, to ease the proofs, we shall proceed with the order-dual of
the poset $T(\mathring{N})$. Indeed, since the first reduced nodes are the
last nodes if we count from the root, as it is standard practice, we shall
reverse that order in the proofs below.

######  Lemma 4.

Let $N$ be an orchard network. The mapping $\sigma$ in Lemma 2 can be
restricted to
$\tilde{\sigma}:\mathrm{CR\text{-}Seq}(N)\to\mathrm{LinExt}(T(\mathring{N})^{\mathrm{op}})$,
this is, the set of linear extensions of the order-dual of the poset
$T(\mathring{N})$.

###### Proof.

Let $S=(N_{0},\ldots,N_{s})\in\mathrm{CR\text{-}Seq}(N)$ and
$\pi=\tilde{\sigma}(S)$. According to the previous observation, we must prove
that $\pi$ is a linear extension of the dual of partial order on
$T(\mathring{N})$ induced by reachability relation of $N$. In other words,
that for any two $u,v\in T(\mathring{N})$ such that $v\rightsquigarrow u$ in
$N$, then $\pi^{-1}(u)\leqslant\pi^{-1}(v)$. By definition, $\pi^{-1}(u)$ is
the largest index $i$ such that $u\in T(\mathring{N}_{i})$ (resp. $j$ for
$v$). Assume that $i>j$, so that we have the following situation:

$\begin{array}[]{ccccccccc}\cdots\supseteq&T(\mathring{N}_{j})&\supseteq&T(\mathring{N}_{j+1})&\supseteq\cdots\supseteq&T(\mathring{N}_{i})&\supseteq&T(\mathring{N}_{i+1})&\supseteq\cdots\\\
&\rotatebox{90.0}{$v\in$}\;\rotatebox{90.0}{$u\in$}&&\rotatebox{90.0}{$v\notin$}\;\rotatebox{90.0}{$u\in$}&&\rotatebox{90.0}{$v\notin$}\;\rotatebox{90.0}{$u\in$}&&\rotatebox{90.0}{$v\notin$}\;\rotatebox{90.0}{$u\notin$}&\end{array}$

We can observe that, at $N_{j+1}$, $v$ is a leaf and $u$ is an internal node,
which contradicts the assumption that $v\rightsquigarrow u$ in $N$. ∎

######  Remark 3.

Since $\sigma=\iota\circ\tilde{\sigma}$, where
$\iota:\mathrm{LinExt}(T(\mathring{N})^{\mathrm{op}})\hookrightarrow\mathfrak{S}$
is the natural inclusion, then $\tilde{\sigma}$ must also be injective.

We shall now present Theorem 5, the main result in this section, stating that
counting cherry reduction sequences of a tree-child network is equivalent to
counting the set of linear extensions of the poset $T(\mathring{N})$.

######  Theorem 5.

Let $N$ be a tree-child network. Then, there is a bijection between the set of
cherry reduction sequences of $N$ and the set of linear extensions of the
poset $T(\mathring{N})$.

###### Proof.

It will be enough to prove that $\tilde{\sigma}$ is surjective, and thus, by
Lemma 2, a bijection. Indeed, consider the following commutative diagram:

${\mathrm{CR\text{-}Seq}(N)}$${\mathfrak{S}}$${\mathrm{LinExt}(T(\mathring{N})^{\mathrm{op}})}$${\mathrm{LinExt}(T(\mathring{N}))}$$\scriptstyle{\cong}$$\scriptstyle{\tilde{\sigma}}$$\scriptstyle{\sigma}$$\scriptstyle{\iota}$$\scriptstyle{\cong}$$\scriptstyle{\mathrm{rev}}$

Notice that, in this diagram, $\mathrm{rev}$ is simply the bijection that
simply reverts the permutations. We can then see that
$\mathrm{rev}\circ\tilde{\sigma}$ provides such bijection.

Let us prove that $\tilde{\sigma}$ is surjective. Let $\pi=(u_{0}\ u_{1}\cdots
u_{s-1})$, $u_{s-1}=\rho$, be a linear extension of the order-dual of the
reachability order in $N$. We want to show that

$(N_{0},\,N_{1}=\mathrm{CR}(N_{0},u_{0}),\,N_{2}=\mathrm{CR}(N_{1},u_{1}),\,\ldots,\,N_{s}=\mathrm{CR}(N_{s-1},u_{s-1}))$

is a cherry reduction sequence for $N=N_{0}$.

We shall proceed by induction over $i\in\\{0,\ldots,s-1\\}$. If $i=0$, then
$\mathrm{CR}(N_{0},u_{0})$ is $N_{1}$. Since $\pi$ is a linear extension, then
$u_{0}$ is maximal in $N$, and thus by Lemma 3, a terminal node in $N$.
Furthermore, $N_{1}$ is still a tree-child network and
$T(\mathring{N}_{1})=T(\mathring{N}_{0})\setminus\\{u_{0}\\}$ (by Lemma 1).

Now assume that the result holds up to $i\in\\{0,\ldots,s-1\\}$; that is, that
$u_{j}$ is a terminal node of $N_{j}$ and that $\mathrm{CR}(N_{j},u_{j})$ is a
tree-child network for any $j\leqslant i$. We shall now prove that it holds
for $i+1$. Now, by the induction hypothesis,
$N_{i+1}=\mathrm{CR}(N_{i},u_{i})$ is a tree-child network. Furthermore,
$u_{i+1}$ is an internal tree node of $N_{i+1}$: indeed, since
$T(\mathring{N}_{i+1})=T(\mathring{N}_{i})\setminus\\{u_{i}\\}$, and $u_{i+1}$
was an internal tree node of $N_{i}$. Now, clearly, $u_{i+1}$ is a maximal
element of the poset $T(\mathring{N}_{i+1})$, because
$\pi|_{T(\mathring{N}_{i+1})}$ begins by $u_{i+1}$. Therefore, it is a
terminal node of $N_{i+1}$, and $\mathrm{CR}(N_{i+1},u_{i+1})$ is a tree-child
network whose set of internal nodes is
$T(\mathring{N}_{i+1})\setminus\\{u_{i+1}\\}$ (Lemma 1). ∎

##  4 Algorithms and complexity

Now that we have established that counting cherry reduction sequences in a
tree-child network is the same as counting linear extensions of the induced
poset of its internal tree nodes, we shall work towards giving an algorithm to
compute this number.

The problem of counting linear extensions of a poset is #P-complete in general
[4], and several algorithms have been proposed to count the number of linear
extensions of posets under different restrictions [1, 12, 13, 18, 20, 21, 22],
or estimating it [5, 9].

The tree-width of a graph has been thoroughly used in order to assess the
complexity of algorithms that count the number of linear extensions. For
instance, in [10] it is shown that the problem of counting the number of
linear extensions of a poset of $p$ elements parameterized by the tree-width
$\mathrm{tw}$ of its underlying cover graph is not fixed-parameter tractable
(FPT), or in other words, there is no algorithm with complexity
$f(\mathrm{tw})p^{O(1)}$ for some computable function $f$. On the other hand,
the level of a phylogenetic network is a commonly used parameter to asses the
complexity of algorithms in phylogenetics. Usually an upper bound of the level
of a network is the easier one to assess, and fortunately the tree-width and
level are related by Lemma 6.

######  Lemma 6 ([17, Observation 2]).

Let $N$ be a level-$k$ network and $r$ its number of reticulations. Then
$\mathrm{tw}(N)\leqslant k+1\leqslant r+1$.

We will follow the lead of [18], where the authors present two algorithms to
count the number of linear extensions of a poset $P$ with $p$ elements, the
first one with complexity $O(2^{p}p)$, and the second one with complexity
$O(p^{\mathrm{tw}+4})$, where $\mathrm{tw}$ is the (undirected) tree-width of
the cover graph of $P$.

######  Theorem 7 ([18, Theorem 1]).

Given a poset $P$, the number of linear extensions of $P$ can be computed in
time $O(p^{\mathrm{tw}+4})$, where $p=\lvert P\rvert$ and $\mathrm{tw}$ is the
tree-width of the cover graph of $P$.

The problem arises when we want to assess the tree-width of the cover graph of
the poset induced over the internal tree nodes of a tree-child network. By
Lemma 8, $\mathcal{C}(T(\mathring{N}))$ is a minor of $N$, and thus
$\mathrm{tw}(\mathcal{C}(T(\mathring{N})))\leqslant\mathrm{tw}(N)$.

Consequently, Theorem 7 provides an algorithm that computes the number of
linear extensions of a tree-child network in time
$O(|T(\mathring{N})|^{k+5})$, where $k$ is the level of $N$, and the number of
internal tree nodes is the number of leaves of the network minus $1$. In other
words, this provides an algorithm that runs in time
$O(|\Sigma|^{\mathrm{tw}+4})\subseteq O(|\Sigma|^{k+5})$.

######  Lemma 8.

Let $N$ be a tree-child network and $N^{\prime}$ the subgraph of $N$ induced
by removing, from $\mathring{N}$, all the reticulation nodes with out-degree
$0$ (in $\mathring{N}$). The DAG resulting from the contraction of every edge
between a reticulation node and its child tree node in $N^{\prime}$ is
isomorphic to the cover graph of $T(\mathring{N})$.

###### Proof.

First, observe that, in this case, the resulting graph after edge contractions
is still directed and acyclic. Now let
$\varphi:\mathcal{C}(T(\mathring{N}))\to N^{\prime}/_{{\displaystyle\\!\sim}}$
defined by the rule $u\mapsto[u]$, where
$N^{\prime}/_{{\displaystyle\\!\sim}}$ is the (quotient) DAG defined in the
statement of this proposition by contracting edges from reticulations to tree
nodes.

Let us first see that $\varphi$ is indeed bijective. To see that the map is
surjective, notice that nodes $[u]$ in $N^{\prime}/_{{\displaystyle\\!\sim}}$
can be either $\\{u\\}$ or $\\{u,h\\}$, where $h$ is a reticulation node. In
both cases, $u\in T(\mathring{N})$ because $N^{\prime}$ does not contain any
reticulation node with leaf children and thus the map is surjective. Now, let
$u,v$ be two tree nodes; if $[u]=[v]$, then either $\\{u\\}=\\{v\\}$ or
$\\{u,h\\}=\\{v,h\\}$, where $h$ is a reticulation node and thus not a tree
node; in both cases, $u=v$.

Let us now see that $\varphi$ preserves and reflects edges. Let $u,v$ be two
internal tree nodes. By definition, we know that
$u\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}v$ if, and only if, there exists a
directed path in $N$ between $u$ and $v$ and there is no tree node
$w\notin\\{u,v\\}$ such that $u\prec w\prec v$; or, equivalently, that either
$uv\in E(N)$ or $uh,hv\in E(N)$ (since the network is tree-child) for some
reticulation node $h$. In any case, this implies that $[u][v]\in
E(N^{\prime}/_{{\displaystyle\\!\sim}})$. Conversely, if $[u][v]\in
E(N^{\prime}/_{{\displaystyle\\!\sim}})$, then we have three cases for
$u^{\prime}\in[u],v^{\prime}\in[v]$ such that $u^{\prime}v^{\prime}\in E(N)$:

  * •

If $u^{\prime}=u$ and $v^{\prime}=v$, then
$u\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}v$.

  * •

If $u^{\prime}$ is a reticulation node, then $[u]=\\{u,u^{\prime}\\}$ and
$v^{\prime}=v$ (because the network is tree-child). Hence
$uu^{\prime},u^{\prime}v\in E(N)$ and
$u\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}v$.

  * •

If $v^{\prime}$ is a reticulation node, then $[v]=\\{v,v^{\prime}\\}$ and
$u^{\prime}=u$ (because the network is tree-child). Hence
$uv^{\prime},v^{\prime}v\in E(N)$ and
$u\prec\mathrel{\mkern-5.0mu}\mathrel{\cdot}v$.

∎

The combination of the algorithm in [18] and Lemma 8 is provided as Algorithm
1. It uses Lemma 8 to first obtain $\mathcal{C}(T(\mathring{N}))$, and then
immeditely returns the result of applying any linear extension-counting
algorithm (named _LEcount_ as in [18]) to its adjacency matrix. Clearly, both
the first step and obtaining the adjacency matrix have complexity at most
$O(\lvert V(N)\rvert^{2})=O(\lvert\Sigma\rvert^{2})$, hence the algorithm’s
complexity is as high as the complexity of the chosen _LEcount_
implementation.

More precisely, the algorithm assumes that the network is provided as an
adjacency list, with nodes numbered from $1$ to $\lvert V(N)\rvert$. As seen
in Lemma 8, the cover graph of $T(\mathring{N})$ is obtained by contracting
edges from a subgraph of $\mathring{N}$. To do this, a mapping (quot) is
constructed by iterating linearly over the nodes $u$ of $N$: leaves are
discarded (quot[u] $=-1$), internal nodes mapped to the next available index
and reticulations $H$ identified with their tree-child $v$ if $v$ is internal
(quot[H] = quot[v]). Note that attention has to be paid in order not to map
the same node twice, both when visited as an internal node and as the child of
a reticulation. Once this mapping is constructed, the cover graph of
$T(\mathring{N})$ is easily obtained by applying it to all the edges of the
input network and then passed to the linear extension-counting algorithm of
choice (in the case of _LEcount_ , the input must be given as an adjacency
matrix).

Input: Tree-child phylogenetic network $N$ as an adjacency list, $LEcount$
function

Output: Number of cherry reduction sequences of $N$

$n\leftarrow\lvert V(N)\rvert$;

/* Build $\mathcal{C}(T(\mathring{N}))$ using Lemma 8 */

$c\leftarrow 0$;

/* To be $\lvert T(\mathring{N})\rvert$ */

/* First, we build a mapping from $1,\ldots,n$ to $-1,1,\ldots,c$ to
remove/merge nodes as a quotient function $V(N)\to
T(\mathring{N})\sqcup\\{-1\\}$ */

$quot\leftarrow[-1,\,\overset{n}{\ldots},\,-1]$;

for  _$u\in V(N)$_ do

/* $u$ is an internal tree node which has not been mapped yet */

if  _$\mathrm{deg}_{\mathrm{out}}^{N}(u)=2$ and $quot[u]<0$_ then

$c\leftarrow c+1$;

$quot[u]\leftarrow c$;

end if

/* $u$ is a reticulation (with a tree-child) */

if  _$\mathrm{deg}_{\mathrm{out}}^{N}(u)=1$_ then

$\\{v\\}\leftarrow N[u]$;

/* Consider $u$ only if its child $v$ is internal */

if  _$\mathrm{deg}_{\mathrm{out}}^{N}(v) >0$_ then

/* Map $v$ first if not visited yet */

if  _$quot[v] <0$_ then

$c\leftarrow c+1$;

$quot[v]\leftarrow c$;

end if

$quot[u]\leftarrow quot[v]$

end if

end if

/* If $\mathrm{deg}_{\mathrm{out}}^{N}(u)=0$, then $u$ is a leaf, skip it */

end for

$coverGraph\leftarrow[\emptyset,\,\overset{c}{\ldots},\,\emptyset]$;

for  _$u\in V(N)$_ do

/* $u$ is an internal tree node */

if  _$\mathrm{deg}_{\mathrm{out}}^{N}(u)=2$_ then

$coverGraph[quot[u]]\leftarrow\\{quot[v]:v\in N[u],\,quot[v]\geqslant 0\\}$;

end if

end for

$M_{\mathcal{C}}\leftarrow adjacencyMatrix(coverGraph)$;

return _LEcount( $M_{\mathcal{C}}$)_;

Algorithm 1 Algorithm for counting cherry reductions using LEcount [18].

In the next section, we shall further study the relationship of tree-child
networks with their tree-width. In particular, we shall see that we can build
tree-child networks of any tree-width, provided (as seen in Lemma 6) that the
level is unbounded.

###  4.1 Tree-child networks of arbitrary tree-width

The restriction to tree-child networks does not seem to simplify the
complexity of the existing algorithms: we shall always be able to build a
tree-child network whose tree-width and level are in a similar order of
magnitude.

######  Proposition 9.

For every $n\geqslant 3$, there exists a level-$\frac{(n-1)(n-2)}{2}$ tree-
child phylogenetic network whose underlying graph has a minor of tree nodes
isomorphic to the clique $K_{n}$. In other words, it has tree-width at least
$n$.

###### Proof.

We explicitly construct said phylogenetic network $N$ as follows: Consider the
set of nodes

$\displaystyle V=$ $\displaystyle\\{u_{ij}:1\leqslant i<j\leqslant
n\\}\cup\\{h_{ij}:2\leqslant i<j\leqslant n\\}$
$\displaystyle\cup\\{v_{ij}:2\leqslant i<j-1,\,j\leqslant
n\\}\cup\\{x_{ij}:2\leqslant i<j-1,\,j\leqslant n\\}$
$\displaystyle\cup\\{z_{j}:1\leqslant j\leqslant n\\}$

and edges defined as

$\displaystyle E_{j}=$
$\displaystyle\,\\{u_{j\ell}u_{j(\ell+1)}:j<\ell<n\\}\cup\\{u_{jn}z_{j}\\}$
($j=1,2$) $\displaystyle E_{j}=$
$\displaystyle\bigcup_{i=2}^{j-2}\\{h_{ij}v_{ij},\,v_{ij}x_{ij},\,v_{ij}h_{(i+1)j}\\}$
($j=3,\,\ldots,\,n-1$) $\displaystyle\cup\\{h_{(j-1)j}u_{j(j+1)}\\}$
$\displaystyle\cup\\{u_{j\ell}u_{j(\ell+1)}:j<\ell<n\\}\cup\\{u_{jn}z_{j}\\}$
$\displaystyle E_{n}=$
$\displaystyle\bigcup_{i=2}^{n-2}\\{h_{in}v_{in},\,v_{in}x_{in},\,v_{in}h_{(i+1)n}\\}\cup\\{h_{(n-1)n}z_{n}\\}$
$\displaystyle E=$
$\displaystyle\bigcup_{j=1}^{n}E_{n}\cup\\{u_{1j}h_{2j}:3\leqslant j\leqslant
n\\}\cup\\{u_{ij}h_{ij}:2\leqslant i<j\leqslant n\\},$

which can also be visualized in Figures 2, 3 and 4. Figure 5 shows two
examples of this network, with $n=3,4$.

${u_{12}}$$u_{23}$$u_{13}$$h_{23}$$u_{14}$

$\ddots$

$\ddots$

$u_{1n}$$h_{2n}$$z_{1}$

${u_{23}}$$u_{12}$$h_{23}$$u_{24}$$h_{24}$$u_{25}$$\ddots$$\ddots$$u_{2n}$$h_{2n}$$z_{2}$

Figure 2: Nodes adjacent to the paths $u_{12}\cdots u_{1n}z_{1}$ (red) and
$u_{23}\cdots u_{2n}z_{2}$ (blue).
$z_{n}$$h_{(n-1)n}$$x_{(n-2)n}$$v_{(n-2)n}$$h_{(n-2)n}$$\ddots$$\ddots$$h_{3n}$$x_{2n}$$v_{2n}$$h_{2n}$$u_{1n}$$u_{2n}$$u_{3n}$$\ddots$$u_{(n-2)n}$$u_{(n-1)n}$
Figure 3: Nodes adjacent to the path $h_{2n}\cdots h_{(n-1)n}z_{n}$
(highlighted in orange).
${u_{j(j+1)}}$$h_{(j-1)j}$$x_{(j-2)j}$$v_{(j-2)j}$$h_{(j-2)j}$$\ddots$$\ddots$$h_{3j}$$x_{2j}$$v_{2j}$$h_{2j}$$u_{1j}$$u_{2j}$$u_{3j}$$\ddots$$u_{(j-2)j}$$u_{(j-1)j}$$h_{j(j+1)}$$u_{j(j+2)}$$h_{j(j+2)}$$u_{j(j+3)}$$\ddots$$\ddots$$u_{jn}$$h_{jn}$$z_{j}$
Figure 4: Nodes adjacent to the path $h_{2j}\cdots h_{(j-1)j}u_{j(j+1)}\cdots
u_{jn}z_{j}$ (highlighted in magenta) for $j=3,\ldots,n-1$.

It is trivial to verify that this is a tree-child phylogenetic network on the
set of nodes labeled as $x_{ij}$ and $z_{j}$ and root $u_{12}$. This network
$N$ consists of a single blob with exit reticulation $h_{(n-1)n}$ and its
total number of reticulations is

$\displaystyle\lvert\\{h_{ij}:2\leqslant i<j\leqslant n\\}\rvert$
$\displaystyle=\sum_{j=3}^{n}\lvert\\{h_{ij}:2\leqslant i<j\\}\rvert$
$\displaystyle=\sum_{j=3}^{n}(j-2)=\sum_{j=1}^{n-2}j=\frac{(n-1)(n-2)}{2}.$

Moreover, removing all leaves of the form $x_{ij}$ and edges $v_{ij}x_{ij}$
incident to them, and contracting the pairwise disjoint paths (highlighted in
Figures 2, 4 and 3)

$\displaystyle u_{12}\cdots u_{1n}z_{1}$ $\displaystyle u_{23}\cdots
u_{2n}z_{2}$ $\displaystyle h_{2j}\cdots h_{(j-1)j}u_{j(j+1)}\cdots
u_{jn}z_{j}$ for $j=3,\ldots,n-1$ $\displaystyle h_{2n}\cdots h_{(n-1)n}z_{n}$

yields an underlying graph which is isomorphic to $K_{n}$. To prove this,
observe that this yields a graph with $n$ nodes, namely $[z_{i}]$ for
$i=1,\ldots n$. Note that there are edges from each $[z_{i}]$ to all other
$[z_{j}]$ for $2\leqslant i<j\leqslant n$: these are witnessed by the edge
$u_{ij}h_{ij}$ connecting $u_{ij}\in[z_{i}]$ and $h_{ij}\in[z_{j}]$. In
addition, there are also edges from $[z_{1}]$ to each other $[z_{j}]$ for
$2<j\leqslant n$ via the edge $u_{1j}h_{2j}$ from $u_{1j}\in[z_{1}]$ to
$h_{2j}\in[z_{j}]$. Finally, there is an edge from $[z_{1}]$ to $[z_{2}]$ via
the edge $u_{12}u_{23}$. ∎

${u_{12}}$$u_{13}$$u_{23}$$h_{23}$$z_{2}$$z_{1}$$z_{3}$
${u_{12}}$$u_{13}$$u_{23}$$h_{23}$$u_{24}$$h_{24}$$z_{2}$$u_{14}$$z_{1}$$u_{34}$$z_{3}$$h_{34}$$z_{4}$$v_{24}$$x_{24}$

Figure 5: The networks constructed in Lemma 9 for $n=3$ and $n=4$.

This is a necessary result: for it could (hypothetically) be the case that the
topological properties of a tree-child network forbade its tree-width to
attain high values (which is, for instance, what happens with trees: its tree-
width is constant). However, we have proved that the tree-width of a tree-
child network is in general unbounded.

###  4.2 Tree-width and level of a tree-child network

In the previous section we showed that there was a tree-child phylogenetic
network with level $O(n^{2})$ such that its tree-width was at least $n$, for
any $n\geqslant 3$. In this last section we shall travel in the opposite
direction, and show that if a phylogenetic network contains a minor with a
fixed number of nodes and edges, then it is possible to find a lower bound of
its level. This is useful to us, because a very widespread characterization of
graph theoretical concepts (and indeed the tree-width) is done in terms of
forbidden minors; i.e., minors whose presence in a graph determines whether it
has a property or not. In the case of the tree-width, for instance, we know
that a graph has tree-width less than $3$ if, and only if, it does not contain
any minor isomorphic to $K_{4}$ [8, p. 327].

######  Lemma 10.

Let $H$ be a weakly connected subgraph of a phylogenetic network, with $d$
nodes of in-degree $0$. Then, there are at least $d-1$ reticulation nodes in
$H$.

###### Proof.

We shall proceed by induction over the number of edges of $H$. If that number
is $1$, then there is exactly one node with in-degree $0$ and there is nothing
to prove.

Assume now that the statement in this proposition is true for $H$ with up to
$m$ edges, let $D_{0}(H)$ be the set of all nodes with in-degree $0$, and
$d=|D_{0}(H)|$. Assume as well that $d\geqslant 2$, for if $d=1$ there is
nothing to prove. Let $u$ be a node with in-degree $0$, and $h$ a reticulation
node such that it descends from $u$ in $H$ and there is no other reticulation
node between $u$ and $h$. Let $H^{\prime}$ be the subgraph obtained from $H$
by deleting the path from $u$ to $h$ except for $h$; i.e., deleting all the
nodes in that path different from $h$ and all the edges with either endpoint
in them. Notice that this path is a strong path and all the nodes in it except
$h$ is a tree node.

Now, $H^{\prime}$ need not be weakly connected. Let
$H_{1}^{\prime},\ldots,H_{s}^{\prime}$ be the weakly connected components of
$H^{\prime}$, each with $d_{i}$ nodes of $D_{0}(H)$. Let $vw$ be a bridge edge
from a node in the path $u\rightsquigarrow h$, say $v$, to a node in
$H_{i}^{\prime}$, say $w$; since $v$ is a tree node, the direction goes from
$v$ to $w$. Two cases arise:

  * •

If $w$ is a tree node in $H$, then $H_{i}^{\prime}$ now has a new node with
in-degree $0$. In this case, $H_{i}^{\prime}$ will have at least $d_{i}+1$
nodes with in-degree $0$ and thus a minimum of $d_{i}$ reticulation nodes by
the induction hypothesis.

  * •

If $w$ is a reticulation node in $H$, it will not be so in $H_{i}^{\prime}$.
In this case $H_{i}^{\prime}$ would have at least $d_{i}$ nodes with in-degree
$0$ and therefore at least $d_{i}-1$ reticulation nodes ($d_{i}$ in $H$).

By definition, $d_{1}+\cdots+d_{s}=d-1$ (because we have removed $u$ from
$H$). Therefore, since each $H_{i}^{\prime}$ contains at least $d_{i}$
reticulation nodes of $H$, we conclude that $H$ has at least $d-1$
reticulation nodes. ∎

Given a minor of a phylogenetic network $N$ (which is, remember, an undirected
graph), we can endow it with an orientation induced by $N$ as follows: if
$\alpha\beta$ (undirected) is an edge in such a minor, then there exist
$u\in\alpha$ and $v\in\beta$ such that either $uv$ or $vu$ (directed) is an
edge in $N$. Say, for instance, that $uv$ is the case; then, endow the
original edge with the direction from $\alpha$ to $\beta$. Note that this does
not prevent the existence of multiple orientations, but the following result
is true nevertheless.

######  Corollary 11.

Let $H/_{{\displaystyle\\!\sim}}$ be a minor of a phylogenetic network $N$,
endowed with an orientation induced by $N$. Let
$\alpha_{1},\ldots,\alpha_{d},\,\beta$ be nodes in
$H/_{{\displaystyle\\!\sim}}$ such that there exist edges
$\alpha_{1}\beta,\ldots,\alpha_{d}\beta$. Then, there exist at least $d-1$
reticulation nodes in $\beta$.

###### Proof.

By definition, there exist $u_{1}\in\alpha_{1},\ldots,\,u_{d}\in\alpha_{d}$
and $v_{1},\ldots,v_{d}\in\beta$ such that $u_{1}v_{1},\ldots,u_{d}v_{d}$ are
edges in $N$. Notice as well that the nodes in $\beta$ induce a weakly
connected subgraph of $N$ (Section 1.7 in [8]). Consider this subgraph,
together with the nodes $u_{1},\ldots,u_{d}$ and the edges
$u_{1}v_{1},\ldots,u_{d}v_{d}$. We now fall under the hypotheses of Lemma 10
and deduce that there are at least $d-1$ reticulations in this graph, none of
which can be $u_{1},\ldots,u_{d}$ and thus must be in $\beta$. ∎

We will now provide a lower bound of the level of a phylogenetic network given
the number of nodes and edges of one of its minor. Since we have not been able
to find a suitable reference in the literature, we present here the result
with its proof.

######  Proposition 12.

Let $N$ be a phylogenetic network and $H$ any biconnected minor of $N$. Then
the level of $N$ is at least $|E(H)|-|V(H)|+1$.

###### Proof.

Let $G$ be the underlying graph of $N$. If there is such a minor of $H$, it
must be contained in a blob $B$ of $N$ (as they are maximal biconnected
components by definition). In addition, recall that any minor of the
underlying graph of $N$ is obtained by removing nodes, edges and contracting
edges from $G$. This process is then described by the quotient of a subgraph
$H^{\prime}$ of $G$ via an equivalence relation $\sim$ (Proposition 1.7.1 in
[8]). Then, the nodes of such a minor $H=H^{\prime}/_{{\displaystyle\\!\sim}}$
are equivalence classes of $V(H^{\prime})$, and there is an edge $[u][v]\in
E(H)$ whenever there is an edge $u^{\prime}v^{\prime}\in E(H^{\prime})$ or
$v^{\prime}u^{\prime}\in E(H^{\prime})$ for some $u^{\prime}\in[u]$ and
$v^{\prime}\in[v]$. For each edge $[u][v]$ in $H$, choose such an edge in
$H^{\prime}$ in order to endow $[u][v]$ with an orientation and obtain a
directed graph with underlying graph $H$. Moreover, one can choose some $r\in
V(H^{\prime})$ with no incoming edges from nodes in $H^{\prime}$ (this is
possible because $N$ is a DAG) and therefore there exists some orientation
such that $\mathrm{deg}_{\mathrm{in}}^{H}([r])=0$.

By Corollary 11 we have that each node $\beta\in V(H)$ (i.e. equivalence class
of weakly connected nodes in $H^{\prime}$) in this directed graph with at
least one incoming edge contains at least
$\mathrm{deg}_{\mathrm{in}}(\beta)-1$ reticulation nodes of $N$. Summing over
all such nodes $\beta\in V(H)$ we obtain a lower bound of the number of
reticulations of the blob and thus the level of $N$:

$\displaystyle|R(B)|$ $\displaystyle\geqslant\sum_{\begin{subarray}{c}\beta\in
V(H)\\\ \mathrm{deg}_{\mathrm{in}}(\beta)\geqslant
1\end{subarray}}(\mathrm{deg}_{\mathrm{in}}(\beta)-1)$
$\displaystyle=\sum_{\beta\in
V(H)}\mathrm{deg}_{\mathrm{in}}(\beta)-\lvert\\{\beta\in
V(H):\mathrm{deg}_{\mathrm{in}}(\beta)\geqslant 1\\}\rvert$
$\displaystyle\geqslant|E(H)|-|V(H)|+1.$

∎

######  Remark 4.

Notice that the number $|E(H)|-|V(H)|+1$ would be equal to the number of
reticulations of $H$ if $H$ was a directed binary network. However, we have
defined our minors to be undirected and not necessarily binary; in the binary
case it is, then, the number of reticulations of a minor endowed with any
orientation.

######  Remark 5.

In the previous three results, we have thoroughly used the fact that our
networks are binary.

In particular, the following two results are useful to relate the level of a
phylogenetic network to is tree-width. In Section 2.1 we saw that if a
phylogenetic network had a minor isomorphic to a clique $K_{n}$, then its
tree-width was at least $n-1$.

######  Corollary 13.

If a phylogenetic network has a minor isomorphic to the clique $K_{n}$, then
its level is at least $\frac{(n-1)(n-2)}{2}$.

A similar result is given for the _grid_. A $n\times m$ grid is the graph on
the set of nodes $\\{1,\ldots,n\\}\times\\{1,\ldots,m\\}$ whose set of edges
is

$\\{(i,j)(i^{\prime},j^{\prime}):|i-i^{\prime}|+|j-j^{\prime}|=1\\}.$

A graph with a minor isomorphic to a $n\times m$ grid has tree-width at least
$\min\\{n,m\\}$ [8, p. 356]. In the following corollary, we give a lower bound
for a phylogenetic network with a minor isomorphic to a $n\times m$ grid.

######  Corollary 14.

If a phylogenetic network has a minor isomorphic to the $n\times m$ grid or
the $n\times m$ complete bipartite graph, then its level is at least
$(n-1)(m-1)$.

Given any forbidden minor of a particular value of the tree-width, Proposition
12 provides a way of finding a lower bound to the level a phylogenetic network
in order for it to present that tree-width.

##  5 Conclusions

In this manuscript, we have reduced the problem of counting the number of
cherry reduction sequences in tree-child networks to the well-studied problem
of counting the number of linear extensions of their reachability order on
tree nodes (Section 3), for which there exist several algorithms whose
complexity depends on the tree-width of the underlying cover graph. In
particular, the problem becomes $O(p^{\mathrm{tw}}$), where $p$ is the number
of elements in the poset and $\mathrm{tw}$ is its tree-width. In this regard,
we have shown (Section 4.1) that the fact that our networks are tree-child
does not imply the existence of a fixed upper bound on their tree-width.
However, the tree-width of a phylogenetic network is bounded by its level. In
this regard, we have given a lower bound of the level (and thus, of the tree-
width) of a tree-child phylogenetic network given the number of nodes and
edges of a minor (Section 4.2), which can be easily applied to any set of
forbidden minors for a given tree-width.

This does not mean, however, that the problem of counting linear extensions in
a tree-child network of a given level is as difficult as that of counting
linear extensions in a general poset whose cover graph has the same level. The
possibility remains open (at least, theoretically) for the existence of an
algorithm specific to tree-child networks that exploits some topological
features in order to find a quicker way to count their linear extensions. As
future work, we would like to study what kind of posets do tree-child networks
define and whether computing the number of linear extensions of these
particular posets is a substantially easier problem than that of general
posets.

On a more practical note, we want to underline that this connection also
provides a way to polynomially approximate the number of cherry reductions by
leveraging the results of [5] and [9, p. 2] on approximating the number of
linear extensions of certain posets. In conclusion, we hope that this
manuscript can point the phylogenetist community to the tools developed to
solve a larger problem.

Acknowledgements. This research was partially supported by the Spanish
Ministry of Economy and Competitiveness and European Regional Development Fund
project PID2021-126114NB-C44 funded by MCIN/AEI/10.13039/501100011033 and by
“ERDF A way of making Europe.”

## References

  * [1] Mike D Atkinson  “On computing the number of linear extensions of a tree”  In _Order_ 7.1 Kluwer Academic Publishers Dordrecht, 1990, pp. 23–25
  * [2] Thomas Bonnin and Jonathan Lombard  “Situer l’analyse phylogénétique entre les sciences historiques et expérimentales”  In _Philosophia Scientiæ. Travaux d’histoire et de philosophie des sciences_ Université Nancy 2, 2019, pp. 131–148
  * [3] Magnus Bordewich and Charles Semple  “Determining phylogenetic networks from inter-taxa distances”  In _Journal of mathematical biology_ 73.2 Springer, 2016, pp. 283–303
  * [4] Graham Brightwell and Peter Winkler  “Counting linear extensions”  In _Order_ 8, 1991, pp. 225–242  DOI: 10.1007/BF00383444
  * [5] Russ Bubley and Martin Dyer  “Faster random generation of linear extensions”  In _Discrete mathematics_ 201.1-3 Elsevier, 1999, pp. 81–88
  * [6] Gabriel Cardona, Francesc Rossello and Gabriel Valiente  “Comparison of Tree-Child Phylogenetic Networks”  In _IEEE/ACM Transactions on Computational Biology and Bioinformatics_ 6 IEEE, 2009, pp. 552–569  DOI: 10.1109/TCBB.2007.70270
  * [7] Gabriel Cardona, Francesc Rosselló and Gabriel Valiente  “Comparison of tree-child phylogenetic networks”  In _IEEE/ACM Transactions on Computational Biology and Bioinformatics_ 6.4 IEEE, 2008, pp. 552–569
  * [8] Reinhard Diestel  “Graph theory”  New York: Springer, 2000
  * [9] Martin Dyer, Alan Frieze and Ravi Kannan  “A random polynomial-time algorithm for approximating the volume of convex bodies”  In _Journal of the ACM (JACM)_ 38.1 ACM New York, NY, USA, 1991, pp. 1–17
  * [10] Eduard Eiben, Robert Ganian, Kustaa Kangas and Sebastian Ordyniak  “Counting linear extensions: Parameterizations by treewidth”  In _Algorithmica_ 81 Springer, 2019, pp. 1657–1683
  * [11] Péter L. Erdős, Charles Semple and Mike Steel  “A class of phylogenetic networks reconstructable from ancestral profiles”  In _Mathematical Biosciences_ 313, 2019, pp. 33–40  DOI: https://doi.org/10.1016/j.mbs.2019.04.009
  * [12] Stefan Felsner and Thibault Manneville  “Linear extensions of N-free orders”  In _Order_ 32.2 Springer, 2015, pp. 147–155
  * [13] Michel Habib and Rolf H Möhring  “On some complexity properties of N-free posets and posets with bounded decomposition diameter”  In _Discrete Mathematics_ 63.2-3 Elsevier, 1987, pp. 157–182
  * [14] Daniel H Huson, Regula Rupp and Celine Scornavacca  “Phylogenetic networks: concepts, algorithms and applications.”  Cambridge University Press, 2010
  * [15] Leo Iersel, Remie Janssen, Mark Jones and Yukihiro Murakami  “Orchard networks are trees with additional horizontal arcs”  In _Bulletin of Mathematical Biology_ 84.8 Springer, 2022, pp. 76  DOI: 10.1007/s11538-022-01037-z
  * [16] Remie Janssen and Yukihiro Murakami  “On cherry-picking and network containment”  In _Theoretical Computer Science_ 856 Elsevier B.V., 2021, pp. 121–150  DOI: 10.1016/j.tcs.2020.12.031
  * [17] Remie Janssen et al.  “Treewidth of display graphs: bounds, brambles and applications”  In _Journal of Graph Algorithms and Applications_ 23.4, 2019, pp. 715–743  DOI: 10.7155/jgaa.00508
  * [18] Kustaa Kangas, Teemu Hankala, Teppo Mikael Niinimäki and Mikko Koivisto  “Counting Linear Extensions of Sparse Posets.”  In _IJCAI_ , 2016, pp. 603–609
  * [19] Sungsik Kong, Joan Carles Pons, Laura Kubatko and Kristina Wicke  “Classes of explicit phylogenetic networks and their biological and mathematical significance”  In _Journal of Mathematical Biology_ 84.6 Springer, 2022, pp. 47  DOI: 10.1007/s00285-022-01746-y
  * [20] Wing-Ning Li, Zhichun Xiao and Gordon Beavers  “On computing the number of topological orderings of a directed acyclic graph”  In _Congressus Numerantium_ 174, 2005, pp. 143–159
  * [21] Rolf H Möhring  “Computationally tractable classes of ordered sets”  In _Algorithms and order_ Springer, 1989, pp. 105–193
  * [22] Marcin Peczarski  “New results in minimum-comparison sorting”  In _Algorithmica_ 40 Springer, 2004, pp. 133–145
  * [23] Neil Robertson and P.D Seymour  “Graph minors. II. Algorithmic aspects of tree-width”  In _Journal of Algorithms_ 7.3, 1986, pp. 309–322  DOI: https://doi.org/10.1016/0196-6774(86)90023-4
  * [24] Charles Semple and Mike Steel  “Phylogenetics”  Oxford University Press on Demand, 2003
  * [25] Leo Van Iersel and Vincent Moulton  “Trinets encode tree-child and level-2 phylogenetic networks”  In _Journal of mathematical biology_ 68.7 Springer, 2014, pp. 1707–1729
  * [26] Leo Van Iersel, Charles Semple and Mike Steel  “Locating a tree in a phylogenetic network”  In _Information Processing Letters_ 110.23 Elsevier, 2010, pp. 1037–1043


of two parts. Part (a) updates the matrix $\bm{W}$ in (9) while keeping
$\bm{\widehat{\mu}}$ and $\bm{\widehat{\Sigma}}$ as they are. Let us call this
a W-step. Part (b) uses the new ‘missingness’ pattern $\bm{W}$ and carries out
an EM-step to update $\bm{\widehat{\mu}}$ and $\bm{\widehat{\Sigma}}$. So each
C-step contains a single W-step and a single EM-step.

A referee asked what would be the effect of increasing the number of W-steps
and/or EM-steps. We studied this by considering 5 settings. The original
setting is denoted as 1W+1EM, so a single W-step and a single EM-step. The
other four settings are, with similar notation, 5W+1EM, 1W+5EM, 5W+5EM, and
10W+10EM. The convergence criterion and everything else in the algorithm was
left unchanged. We ran 100 replications of the algorithm versions, for the
following combinations of choices. The dimension $d$ is either 10 (with
$n=100$), 20 (with $n=400$), or 40 (with $n=800$), and the true $\Sigma$ is
either A09 or ALYZ. The contamination fraction $\varepsilon$ is 0, 0.1, or 0.2
. And finally, the position of the cellwise outliers is given by $\gamma$
equal to 4 or 10.

As expected, increasing the number of W-steps and/or EM-steps increases the
overall computation time. This is seen in Table 9 which provides the averaged
computation time over all settings in each of the three dimensions. Note that
W-steps are more expensive than EM-steps, due to frequent evaluations of the
objective function. The table shows that increasing the number of steps is
costly, especially in the higher dimensions.

Table 9: Average computation times (in seconds) of algorithm versions. version | d=10 | d=20 | d=40
---|---|---|---
1W + 1EM | 0.42 | 2.72 | 26.24
5W + 1EM | 0.83 | 10.02 | 118.78
1W + 5EM | 0.61 | 4.31 | 32.32
5W + 5EM | 1.13 | 11.74 | 125.77
10W + 10EM | 2.20 | 23.16 | 250.44

The main question is of course whether the faster 1W+1EM version pays a price
in estimation accuracy. The next three tables say that it does not, as the
differences in MSE($\widehat{\mu}$), KLdiv($\widehat{\Sigma}$) and the
objective function were tiny. Also, the effect is not systematic: more
computation time does not necessarily yield a lower MSE($\widehat{\mu}$),
KLdiv($\widehat{\Sigma}$), or objective.

|  |  |  | A09 |  |  | ALYZ |
---|---|---|---|---|---|---|---|---
$\varepsilon$ | $\gamma$ | method | MSE($\widehat{\mu}$) | KLdiv($\widehat{\Sigma}$) | objective | MSE($\widehat{\mu}$) | KLdiv($\widehat{\Sigma}$) | objective
0 | – | 1W + 1EM | 0.01001 | 1.228 | 1289.27 | 0.00998 | 0.846 | 2286.53
0 | – | 5W + 1EM | 0.00998 | 1.243 | 1289.66 | 0.01000 | 0.844 | 2286.49
0 | – | 1W + 5EM | 0.00998 | 1.233 | 1289.19 | 0.01000 | 0.846 | 2286.53
0 | – | 5W + 5EM | 0.00998 | 1.244 | 1289.55 | 0.01002 | 0.845 | 2286.41
0 | – | 10W + 10EM | 0.00998 | 1.244 | 1289.55 | 0.01002 | 0.845 | 2286.41
0.1 | 4 | 1W + 1EM | 0.01050 | 1.323 | 1613.00 | 0.01139 | 1.141 | 2789.84
0.1 | 4 | 5W + 1EM | 0.01046 | 1.303 | 1612.90 | 0.01132 | 1.138 | 2789.59
0.1 | 4 | 1W + 5EM | 0.01050 | 1.300 | 1613.27 | 0.01137 | 1.136 | 2790.15
0.1 | 4 | 5W + 5EM | 0.01040 | 1.293 | 1612.79 | 0.01134 | 1.138 | 2789.58
0.1 | 4 | 10W + 10EM | 0.0104 | 1.293 | 1612.79 | 0.01134 | 1.138 | 2789.58
0.1 | 10 | 1W + 1EM | 0.01043 | 1.418 | 1714.75 | 0.01094 | 1.118 | 2828.22
0.1 | 10 | 5W + 1EM | 0.01043 | 1.416 | 1714.92 | 0.01092 | 1.121 | 2828.31
0.1 | 10 | 1W + 5EM | 0.01038 | 1.421 | 1714.67 | 0.01096 | 1.121 | 2828.22
0.1 | 10 | 5W + 5EM | 0.01041 | 1.418 | 1714.89 | 0.01092 | 1.121 | 2828.32
0.1 | 10 | 10W + 10EM | 0.01041 | 1.418 | 1714.89 | 0.01092 | 1.121 | 2828.32
0.2 | 4 | 1W + 1EM | 0.01180 | 2.710 | 2034.65 | 0.01568 | 3.473 | 3119.95
0.2 | 4 | 5W + 1EM | 0.01181 | 2.748 | 2034.04 | 0.01559 | 3.359 | 3119.06
0.2 | 4 | 1W + 5EM | 0.01179 | 2.745 | 2036.07 | 0.01549 | 3.455 | 3118.36
0.2 | 4 | 5W + 5EM | 0.01184 | 2.768 | 2035.55 | 0.01571 | 3.369 | 3119.30
0.2 | 4 | 10W + 10EM | 0.01184 | 2.768 | 2035.55 | 0.01571 | 3.369 | 3119.30
0.2 | 10 | 1W + 1EM | 0.01109 | 1.795 | 2109.86 | 0.01223 | 2.009 | 3324.95
0.2 | 10 | 5W + 1EM | 0.01099 | 1.794 | 2109.43 | 0.01224 | 2.015 | 3324.98
0.2 | 10 | 1W + 5EM | 0.01104 | 1.774 | 2110.05 | 0.01222 | 2.025 | 3325.00
0.2 | 10 | 5W + 5EM | 0.01096 | 1.780 | 2109.32 | 0.01226 | 2.025 | 3325.05
0.2 | 10 | 10W + 10EM | 0.01096 | 1.779 | 2109.33 | 0.01229 | 2.021 | 3325.09
Table 10: Comparison of different algorithm versions on data with d=10 and n=100. |  |  |  | A09 |  |  | ALYZ |
---|---|---|---|---|---|---|---|---
$\varepsilon$ | $\gamma$ | method | MSE($\widehat{\mu}$) | KLdiv($\widehat{\Sigma}$) | objective | MSE($\widehat{\mu}$) | KLdiv($\widehat{\Sigma}$) | objective
0 | – | 1W + 1EM | 0.00242 | 1.151 | 9694.82 | 0.00247 | 0.830 | 19346.52
0 | – | 5W + 1EM | 0.00242 | 1.154 | 9694.30 | 0.00246 | 0.831 | 19346.57
0 | – | 1W + 5EM | 0.00243 | 1.153 | 9694.68 | 0.00247 | 0.830 | 19346.57
0 | – | 5W + 5EM | 0.00243 | 1.155 | 9694.24 | 0.00246 | 0.829 | 19346.72
0 | – | 10W + 10EM | 0.00243 | 1.155 | 9694.24 | 0.00246 | 0.829 | 19346.72
0.1 | 4 | 1W + 1EM | 0.00251 | 1.185 | 12451.15 | 0.00283 | 1.216 | 23240.19
0.1 | 4 | 5W + 1EM | 0.00252 | 1.186 | 12446.70 | 0.00283 | 1.211 | 23240.16
0.1 | 4 | 1W + 5EM | 0.00251 | 1.189 | 12450.67 | 0.00284 | 1.213 | 23240.50
0.1 | 4 | 5W + 5EM | 0.00251 | 1.187 | 12446.52 | 0.00283 | 1.215 | 23240.09
0.1 | 4 | 10W + 10EM | 0.00251 | 1.187 | 12446.51 | 0.00283 | 1.215 | 23240.09
0.1 | 10 | 1W + 1EM | 0.00248 | 1.256 | 13289.50 | 0.00267 | 1.214 | 23693.20
0.1 | 10 | 5W + 1EM | 0.00248 | 1.257 | 13288.34 | 0.00266 | 1.215 | 23693.08
0.1 | 10 | 1W + 5EM | 0.00248 | 1.259 | 13289.29 | 0.00267 | 1.214 | 23693.38
0.1 | 10 | 5W + 5EM | 0.00248 | 1.255 | 13288.59 | 0.00267 | 1.220 | 23692.84
0.1 | 10 | 10W + 10EM | 0.00248 | 1.255 | 13288.59 | 0.00267 | 1.219 | 23692.84
0.2 | 4 | 1W + 1EM | 0.00270 | 2.086 | 15592.22 | 0.00386 | 3.346 | 25257.25
0.2 | 4 | 5W + 1EM | 0.00270 | 2.102 | 15590.99 | 0.00385 | 3.375 | 25258.53
0.2 | 4 | 1W + 5EM | 0.00271 | 2.081 | 15592.68 | 0.00383 | 3.338 | 25258.51
0.2 | 4 | 5W + 5EM | 0.00271 | 2.092 | 15590.41 | 0.00386 | 3.354 | 25257.58
0.2 | 4 | 10W + 10EM | 0.00270 | 2.091 | 15590.34 | 0.00386 | 3.345 | 25257.52
0.2 | 10 | 1W + 1EM | 0.00260 | 1.593 | 16725.02 | 0.00321 | 1.952 | 27383.61
0.2 | 10 | 5W + 1EM | 0.00259 | 1.588 | 16722.75 | 0.00321 | 1.957 | 27383.51
0.2 | 10 | 1W + 5EM | 0.00259 | 1.589 | 16724.92 | 0.00321 | 1.953 | 27383.79
0.2 | 10 | 5W + 5EM | 0.00259 | 1.586 | 16723.12 | 0.00322 | 1.970 | 27383.19
0.2 | 10 | 10W + 10EM | 0.00259 | 1.586 | 16723.17 | 0.00322 | 1.969 | 27383.08
Table 11: Comparison of different algorithm versions on data with d=20 and n = 400. |  |  |  | A09 |  |  | ALYZ |
---|---|---|---|---|---|---|---|---
$\varepsilon$ | $\gamma$ | method | MSE($\widehat{\mu}$) | KLdiv($\widehat{\Sigma}$) | objective | MSE($\widehat{\mu}$) | KLdiv($\widehat{\Sigma}$) | objective
0 | – | 1W + 1EM | 0.00122 | 2.184 | 37556.92 | 0.00126 | 1.937 | 79272.01
0 | – | 5W + 1EM | 0.00122 | 2.188 | 37556.93 | 0.00126 | 1.931 | 79272.70
0 | – | 1W + 5EM | 0.00122 | 2.186 | 37556.64 | 0.00126 | 1.939 | 79271.40
0 | – | 5W + 5EM | 0.00122 | 2.188 | 37557.10 | 0.00126 | 1.931 | 79272.81
0 | – | 10W + 10EM | 0.00122 | 2.188 | 37557.10 | 0.00126 | 1.931 | 79272.81
0.1 | 4 | 1W + 1EM | 0.00126 | 2.279 | 49674.77 | 0.00153 | 2.808 | 92440.95
0.1 | 4 | 5W + 1EM | 0.00126 | 2.273 | 49659.15 | 0.00153 | 2.801 | 92441.82
0.1 | 4 | 1W + 5EM | 0.00126 | 2.281 | 49673.60 | 0.00153 | 2.816 | 92441.39
0.1 | 4 | 5W + 5EM | 0.00126 | 2.275 | 49658.97 | 0.00153 | 2.809 | 92439.42
0.1 | 4 | 10W + 10EM | 0.00126 | 2.275 | 49658.97 | 0.00153 | 2.804 | 92440.26
0.1 | 10 | 1W + 1EM | 0.00125 | 2.325 | 51862.73 | 0.00142 | 2.943 | 95432.80
0.1 | 10 | 5W + 1EM | 0.00126 | 2.321 | 51857.96 | 0.00142 | 2.922 | 95434.68
0.1 | 10 | 1W + 5EM | 0.00125 | 2.329 | 51862.62 | 0.00141 | 2.933 | 95433.13
0.1 | 10 | 5W + 5EM | 0.00125 | 2.320 | 51858.69 | 0.00142 | 2.934 | 95433.04
0.1 | 10 | 10W + 10EM | 0.00125 | 2.320 | 51858.69 | 0.00142 | 2.936 | 95433.03
0.2 | 4 | 1W + 1EM | 0.00129 | 4.083 | 65008.14 | 0.00201 | 9.206 | 99283.76
0.2 | 4 | 5W + 1EM | 0.00130 | 4.121 | 65001.05 | 0.00201 | 9.311 | 99286.22
0.2 | 4 | 1W + 5EM | 0.00129 | 4.087 | 65007.01 | 0.00201 | 9.261 | 99286.68
0.2 | 4 | 5W + 5EM | 0.00130 | 4.119 | 64999.17 | 0.00202 | 9.297 | 99285.07
0.2 | 4 | 10W + 10EM | 0.00130 | 4.120 | 64999.05 | 0.00202 | 9.297 | 99285.13
0.2 | 10 | 1W + 1EM | 0.00127 | 3.515 | 67014.48 | 0.00170 | 4.313 | 108819.48
0.2 | 10 | 5W + 1EM | 0.00127 | 3.523 | 67009.90 | 0.00169 | 4.330 | 108819.88
0.2 | 10 | 1W + 5EM | 0.00126 | 3.521 | 67016.49 | 0.00170 | 4.338 | 108819.34
0.2 | 10 | 5W + 5EM | 0.00127 | 3.517 | 67009.13 | 0.00169 | 4.333 | 108819.46
0.2 | 10 | 10W + 10EM | 0.00127 | 3.517 | 67009.25 | 0.00169 | 4.321 | 108819.65
Table 12: Comparison of different algorithm versions on data with d=40 and n =
800.

### A.6.4 Results for other variations on the method

Figures 5 and 6 in the paper show the Kullback-Leibler discrepancy of several
covariance estimators in dimensions 10, 20, and 40. Referees requested two
more estimators to be considered:

  * •

the initial estimator DDCW, which is fast as seen from its entries in Table 1
in the paper;

  * •

cellMCD without the penalty term, that is, setting all $q_{j}=0$. We denote
this as cellMCD_q0 .

Figure 10 below plots both versions, together with the curve for cellMCD shown
in Figures 5 and 6 in the paper. We see that DDCW and cellMCD_q0 do not
explode in the sense that the effect of contaminated cells remains bounded,
which is what we want for our initial estimator DDCW. However, cellMCD_q0 has
a large discrepancy, because always taking out 25% of the cells in each
variable hurts efficiency. DDCW does reasonably well by itself under A09, but
very poorly under ALYZ. Neither version can thus be considered a competitive
alternative to cellMCD.

Figure 10: Kullback-Leibler discrepancy of estimated covariance matrices for
$n=100$ (top), $n=400$ (middle) and $n=800$ (bottom), for ALYZ (left) and A09
(right), with $\varepsilon=0.1$.

## Additional References

  * Aubry et al. (2021) Aubry, A., A. De Maio, S. Marano, and M. Rosamilia (2021).  Structured covariance matrix estimation with missing (complex) data for radar applications via expectation-maximization.  IEEE Transactions on Signal Processing 69, 5920–5934.
  * Petersen and Pedersen (2012) Petersen, K. B. and M. S. Pedersen (2012).  The Matrix Cookbook.  Technical University of Denmark.
  * Sun et al. (2020) Sun, Q., Zhou, W and Fan, J. (2020).  Adaptive Huber regression.  Journal of the American Statistical Association 115, 254–265.


* [188] M. He, W. Gu, Y. Kong, L. Zhang, C. J. Spanos, and K. M. Mosalam, “Causalbg: Causal recurrent neural network for the blood glucose inference with iot platform,” _IEEE Internet of Things Journal_ , vol. 7, no. 1, pp. 598–610, 2020.
  * [189] D. Nguyen, P. Pathirana, M. Ding, and A. Seneviratne, “Secure computation offloading in blockchain based iot networks with deep reinforcement learning,” _IEEE Transactions on Network Science and Engineering (Early Access Article)_ , 2021.
  * [190] J. Liang, L. Li, and C. Zhao, “A transfer learning approach for compressed sensing in 6g-iot,” _IEEE Internet of Things Journal (Early Access Article)_ , 2021.
  * [191] Y. Hailemariam, A. Yazdinejad, R. M. Parizi, G. Srivastava, and A. Dehghantanha, “An empirical evaluation of ai deep explainable tools,” in _2020 IEEE Globecom Workshops (GC Wkshps_ , 2020, pp. 1–6.
  * [192] A. Yazdinejad, R. M. Parizi, A. Dehghantanha, H. Karimipour, G. Srivastava, and M. Aledhari, “Enabling drones in the internet of things with decentralized blockchain-based security,” _IEEE Internet of Things Journal_ , vol. 8, no. 8, pp. 6406–6415, 2021.
  * [193] M. Woźniak, J. Siłka, M. Wieczorek, and M. Alrashoud, “Recurrent neural network model for iot and networking malware threat detection,” _IEEE Transactions on Industrial Informatics_ , vol. 17, no. 8, pp. 5583–5594, 2021\.
  * [194] T.-V. Nguyen, T.-N. Tran, K. Shim, T. Huynh-The, and B. An, “A deep-neural-network-based relay selection scheme in wireless-powered cognitive iot networks,” _IEEE Internet of Things Journal_ , vol. 8, no. 9, pp. 7423–7436, 2021.
  * [195] J. Jeon, J. H. Park, and Y.-S. Jeong, “Dynamic analysis for iot malware detection with convolution neural network model,” _IEEE Access_ , vol. 8, pp. 96 899–96 911, 2020.
  * [196] D. Vasan, M. Alazab, S. Venkatraman, J. Akram, and Z. Qin, “Mthael: Cross-architecture iot malware detection based on neural network advanced ensemble learning,” _IEEE Transactions on Computers_ , vol. 69, no. 11, pp. 1654–1667, 2020.
  * [197] T. Zhang, A. Song, X. Dong, Y. Shen, and J. Ma, “Privacy-preserving asynchronous grouped federated learning for iot,” _IEEE Internet of Things Journal (Early Access Article)_ , 2021.
  * [198] J. Zhang, M. Z. A. Bhuiyan, Y. Xu, A. K. Singh, D. F. Hsu, and E. Luo, “Trustworthy target tracking with collaborative deep reinforcement learning in edgeai-aided iot,” _IEEE Transactions on Industrial Informatics (Early Access Article)_ , 2021.
  * [199] A. M. Ghosh and K. Grolinger, “Deep learning: Edge-cloud data analytics for iot,” in _Proceedings of IEEE Canadian Conference of Electrical and Computer Engineering (CCECE)_ , Edmonton, AB, Canada, May 2019.
  * [200] S. Xu, Y. Li, S. Guo, C. Lei, D. Liu, and X. Qiu, “Cloud-edge collaborative sfc mapping for industrial iot using deep reinforcement learning,” _IEEE Transactions on Industrial Informatics (Early Access Article)_ , 2021\.
  * [201] J.-S. Wu and M.-S. Jian, “Smart home personalizing services based on adaptive cloud iot devices with bigdata and deep learning technique,” in _Proceedings of IEEE International Conference on Consumer Electronics - Taiwan (ICCE-TW)_ , Yilan, Taiwan, May 2019.
  * [202] G. Zhang, S. Ni, and P. Zhao, “Keynote 3: Towards a hybrid edge-cloud platform for self-adaptive machine learning based iot applications,” in _Proceedings of Seventh International Conference on Software Defined Systems (SDS)_ , Paris, France, April 2020.
  * [203] B. Dias, A. Glória, and P. Sebastião, “Prediction of link quality for iot cloud communications supported by machine learning,” in _Proceedings of IEEE World AI IoT Congress (AIIoT)_ , Seattle, WA, USA, May 2021.
  * [204] A. Yazdinejad, A. Bohlooli, and K. Jamshidi, “P4 to sdnet: Automatic generation of an efficient protocol-independent packet parser on reconfigurable hardware,” in _2018 8th International Conference on Computer and Knowledge Engineering (ICCKE)_. IEEE, 2018, pp. 159–164.
  * [205] A. Yazdinejad, S. Kavei, and S. Razaghi Karizno, “Increasing the performance of reactive routing protocol using the load balancing and congestion control mechanism in manet,” _Computer and Knowledge Engineering_ , vol. 2, no. 1, pp. 33–42, 2019.
  * [206] S. Duan, D. Zhang, Y. Wang, L. Li, and Y. Zhang, “Jointrec: A deep-learning-based joint cloud video recommendation framework for mobile iot,” _IEEE Internet of Things Journal_ , vol. 7, no. 3, pp. 1655–1666, 2020\.
  * [207] Q. Zhang, L. T. Yang, Z. Chen, P. Li, and F. Bu, “An adaptive dropout deep computation model for industrial iot big data learning with crowdsourcing to cloud computing,” _IEEE Transactions on Industrial Informatics_ , vol. 15, no. 4, pp. 2330–2337, 2019.
  * [208] X. Zhou, X. Xu, W. Liang, Z. Zeng, and Z. Yan, “Deep-learning-enhanced multitarget detection for end–edge–cloud surveillance in smart iot,” _IEEE Internet of Things Journal_ , vol. 8, no. 16, pp. 12 588–12 596, 2021\.
  * [209] C. Pham, D. T. Nguyen, N. H. Tran, K. K. Nguyen, and M. Cheriet, “Learning framework for iot services chain implementation in edge cloud platform,” in _Proceedings of IEEE International Conference on Communications (ICC)_ , Dublin, Ireland, June 2020.
  * [210] ——, “Optimized iot service chain implementation in edge cloud platform: A deep learning framework,” _IEEE Transactions on Network and Service Management_ , vol. 18, no. 1, pp. 538–551, 2021.
  * [211] L. Chen, Y. Xu, Z. Lu, J. Wu, K. Gai, P. C. K. Hung, and M. Qiu, “Iot microservice deployment in edge-cloud hybrid environment using reinforcement learning,” _IEEE Internet of Things Journal_ , vol. 8, no. 16, pp. 12 610–12 622, 2021.
  * [212] Q. Wu, K. He, and X. Chen, “Personalized federated learning for intelligent iot applications: A cloud-edge based framework,” _IEEE Open Journal of the Computer Society_ , vol. 1, no. 1, pp. 35–44, 2020.
  * [213] X. Chen, J. Zhang, B. Lin, Z. Chen, K. Wolter, and G. Min, “Energy-efficient offloading for dnn-based smart iot systems in cloud-edge environments,” _IEEE Transactions on Parallel and Distributed Systems_ , vol. 33, no. 3, pp. 683–697, 2022.
  * [214] C. Qiu, X. Wang, H. Yao, J. Du, F. R. Yu, and S. Guo, “Networking integrated cloud–edge–end in iot: A blockchain-assisted collective q-learning approach,” _IEEE Internet of Things Journal_ , vol. 8, no. 16, pp. 12 694–12 704, 2021.
  * [215] S. Sakib, M. M. Fouda, Z. M. Fadlullah, and N. Nasser, “Migrating intelligence from cloud to ultra-edge smart iot sensor based on deep learning: An arrhythmia monitoring use-case,” in _Proceedings of International Wireless Communications and Mobile Computing (IWCMC)_ , Limassol, Cyprus, June 2020\.
  * [216] M. N and A. A. U, “Cloud-based flood prediction using iot devices and machine learning algorithms,” in _Proceedings of Second International Conference on Electronics and Sustainable Communication Systems (ICESC)_ , Coimbatore, India, August 2021.
  * [217] M. Hussain, S. Aleem, A. Karim, F. Ghazanfar, M. Hai, and K. Hussain, “Design of low cost, energy efficient, iot enabled, air quality monitoring system with cloud based data logging, analytics and ai,” in _Proceedings of International Conference on Emerging Trends in Smart Technologies (ICETST)_ , Karachi, Pakistan, March 2020.
  * [218] A. Srinivasan, N. Natarajan, R. V. Karunakaran, R. Elangovan, A. Shankar, P. M. Sabharish, B. S. Sreeja, and S. Radha, “Elder care system using iot and machine learning in aws cloud,” in _Proceedings of IEEE 17th International Conference on Smart Communities: Improving Quality of Life Using ICT, IoT and AI (HONET)_ , Charlotte, NC, USA, December 2020.
  * [219] N. Abdennadher, “Keynote 3: Towards a hybrid edge-cloud platform for self-adaptive machine learning based iot applications,” in _Proceedings of Fifth International Conference on Fog and Mobile Edge Computing (FMEC)_ , Paris, France, April 2020.
  * [220] J. N. A. Kumar and S. Suresh, “A proposal of smart hospital management using hybrid cloud, iot, ml, and ai,” in _Proceedings of International Conference on Communication and Electronics Systems (ICCES)_ , Coimbatore, India, July 2019.
  * [221] P. Ferrari, S. Rinaldi, E. Sisinni, F. Colombo, F. Ghelfi, D. Maffei, and M. Malara, “Performance evaluation of full-cloud and edge-cloud architectures for industrial iot anomaly detection based on deep learning,” in _Proceedings of II Workshop on Metrology for Industry 4.0 and IoT (MetroInd4.0 &IoT)_, Naples, Italy, June 2019.
  * [222] B. Qolomany, I. Mohammed, A. Al-Fuqaha, M. Guizani, and J. Qadir, “Trust-based cloud machine learning model selection for industrial iot and smart city services,” _IEEE Internet of Things Journal_ , vol. 8, no. 4, pp. 2943–2958, 2021.
  * [223] M. M. Moussa and L. Alazzawi, “Cyber attacks detection based on deep learning for cloud-dew computing in automotive iot applications,” in _Proceedings of IEEE International Conference on Smart Cloud (SmartCloud)_ , Washington, DC, USA, November 2020.
  * [224] C. Thirumallai, M. S. Mekala, V. Perumal, P. Rizwan, and A. H. Gandomi, “Machine learning inspired phishing detection (pd) for efficient classification and secure storage distribution (ssd) for cloud-iot application,” in _Proceedings of IEEE Symposium Series on Computational Intelligence (SSCI)_ , Canberra, ACT, Australia, December 2020.
  * [225] N. Ravi and S. M. Shalinie, “Learning-driven detection and mitigation of ddos attack in iot via sdn-cloud architecture,” _IEEE Internet of Things Journal_ , vol. 7, no. 4, pp. 3559–3570, 2020.
  * [226] R. Alghamdi and M. Bellaiche, “A deep intrusion detection system in lambda architecture based on edge cloud computing for iot,” in _Proceedings of 4th International Conference on Artificial Intelligence and Big Data (ICAIBD)_ , Chengdu, China, May 2021.
  * [227] O. Alkadi, N. Moustafa, B. Turnbull, and K.-K. R. Choo, “A deep blockchain framework-enabled collaborative intrusion detection for protecting iot and cloud networks,” _IEEE Internet of Things Journal_ , vol. 8, no. 12, pp. 9463–9472, 2021.
  * [228] Y. Li, A. H. Aghvami, and D. Dong, “Intelligent trajectory planning in uav-mounted wireless networks: A quantum-inspired reinforcement learning perspective,” _IEEE Wireless Communications Letters (Early Access Article)_ , pp. 1–1, 2021.
  * [229] Q. Wei, H. Ma, C. Chen, and D. Dong, “Deep reinforcement learning with quantum-inspired experience replay,” _IEEE Transactions on Cybernetics (Early Access Article)_ , pp. 1–1, 2021.
  * [230] N. Masuyama, C. K. Loo, M. Seera, and N. Kubota, “Quantum-inspired multidirectional associative memory with a self-convergent iterative learning,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 29, no. 4, pp. 1058–1068, 2018.
  * [231] D. Dong, C. Chen, J. Chu, and T.-J. Tarn, “Robust quantum-inspired reinforcement learning for robot navigation,” _IEEE/ASME Transactions on Mechatronics_ , vol. 17, no. 1, pp. 86–97, 2012.
  * [232] O. P. Patel, N. Bharill, A. Tiwari, and M. Prasad, “A novel quantum-inspired fuzzy based neural network for data classification,” _IEEE Transactions on Emerging Topics in Computing_ , vol. 9, no. 2, pp. 1031–1044, 2021.