Orchard Networks are Trees with Additional Horizontal Arcs

Phylogenetic networks are used in biology to represent evolutionary histories. The class of orchard phylogenetic networks was recently introduced for their computational benefits, without any biological justification. Here, we show that orchard networks can be interpreted as trees with additional \emph{horizontal} arcs. Therefore, they are closely related to tree-based networks, where the difference is that in tree-based networks the additional arcs do not need to be horizontal. Then, we use this new characterization to show that the space of orchard networks is connected under the rNNI rearrangement move, with a diameter of at most $4kn+n\lceil \log_2(n) \rceil +2k+6n-8$.


Introduction
Phylogenetic trees and networks are used in biology to represent evolutionary histories. Trees primarily show the vertical evolutionary processes, whereas networks are used to augment this view with the inclusion of horizontal, or reticulate, processes such as horizontal gene transfer, hybridization, and recombination [BvIJ + 13, EOZN19,BA21].
Sometimes, only a subset of all phylogenetic networks is considered, either to ease the computation of a good representation of the actual evolutionary history (e.g., [vIM14, BST18, ESS19, vIJJ + 21a, BvIJK20]), or because the evolutionary history is expected to have a certain structure (e.g., [MAVE19]). Examples of such subsets are the classes of phylogenetic networks called "tree-child" networks, "tree-based" networks, and "temporal" networks. Tree-based networks are mainly used for their biological interpretation as a tree with additional arcs (e.g., [FS15,CPR15,FGH + 20]). Temporal and tree-child networks are especially interesting because of their computation benefits and nice mathematical properties. Tree-child networks can be biologically interpreted as networks in which each reticulate event leaves a trace in the genetic information of the studied species [CRV08,MAVE19]. Networks with a temporal labelling can be biologically interpreted as networks where each reticulation represents a hybrid speciation event [MNW + 04,BSS06]. Networks that are tree-child and have a temporal labelling are sometimes simply called temporal [HLS13]. It should be noted though that extinctions or undersampling may lead to phylogenetic networks that are not temporal or not tree-based.
Another class of networks is the class of orchard networks, which were recently introduced for their computational benefits [JM21,ESS19] while being more general than tree-child networks. They are usually defined as networks that can be reduced by a series of cherry-picking actions (for this reason, they were called "cherry picking networks" in [JM21]). This comes up naturally when one builds networks by repeatedly considering pairs of taxa that seem to be closely related in the data [BST18, vIJJ + 21a, ESS19,BESS21]. Recently, it was shown that they can be characterized more structurally using acyclic cherry covers [vIJJ + 21b].
In this paper, we show that orchard networks can also be characterized in a very natural way. We prove that orchard networks are precisely those phylogenetic networks that can be obtained from a phylogenetic tree by inserting horizontal arcs, see Figure 1 for an example. Hence, they are closely related to LGT networks [PSC19] except that orchard networks do not (necessarily) specify which arcs are LGT-arcs. Our characterization of orchard networks is similar to the previously mentioned concept of tree-based networks, which are those networks that can be obtained from a phylogenetic tree, called a base tree, by inserting arcs, called linking arcs. The difference is that for orchard networks the linking arcs need to be horizontal while for tree-based networks they do not.
Our characterization of orchard networks can be seen as a time-consistency property, which we call an "HGT-consistent labelling". It basically says that orchard networks are consistent with an evolutionary history in time in which reticulate events represent instantaneous (horizontal) transfers such as LGT events. This is similar, but not the same, as the notion of time-consistency, or temporal labelling, that is commonly found in Figure 1: A network on taxa within the γ-Proteobacteria class with two reticulate events [NRW05]. The dotted arcs with the arrowheads illustrate the passing of genetic material via a horizontal transfer. In this and all subsequent figures, the non-horizontal arcs without arrowheads are directed downwards. The network is a binary orchard network, since it can be reduced by a sequence of cherry reductions (see Section 2.1 for formal definitions of such reductions). One possible sequence that would reduce the network is (1, 2)(3, 4)(2, 4)(5, 6)(4, 6)(7, 8)(9, 8)(10, 6)(6, 8)(8, 9)(9, 10)(11, 12)(12, 13)(10, 13).
the phylogenetic networks literature [MNW + 04,BSS06]. The difference is that in a temporal labelling both arcs entering a reticulation need to be horizontal, which is more natural when reticulations represent hybridization events. This notion has been widely popular in defining network classes, which have been explored in relation to metrics [CLRV08], encodings [CLRV08], and reconstruction methods [BvIJK20]. Another related notion of time-consistency was introduced in [ELR06], which allows bidirectional horizontal arcs as well.
Unlike the other definitions of orchard networks, the "HGT-consistent labelling" that we introduce here can easily be interpreted biologically. This makes the class of orchard networks even more relevant, as it has a natural biological interpretation as a tree with horizontal arcs. Nevertheless, as with the classes of temporal and tree-based networks, extinctions or undersampling may lead to networks that are not orchard, because one or more LGT arcs need to be drawn forward in time.
To showcase the mathematical utility of the new characterization, we use it to prove that the space of orchard networks is connected under rNNI moves. Connectedness of search spaces under rearrangement moves, such as the rNNI move, is important because of their use in local search heuristics and Bayesian methods in phylogenetics (e.g., [MAVE19, BVBS + 19, WYZN18]). Although it has already been proven that rearrangement moves are sufficient to connect several classes of networks [BLS17,Kla20,EFM21], the connectedness of the space of orchard networks has not been investigated yet.
In this paper, we fill this gap in the literature, which may have resulted from the late introduction of this relatively new class of networks. Because orchard networks naturally occur as results of statistical models for network generation, such as the level-k LGT networks from [PSC19], this result may prove to be especially important. Indeed, our results then show that it is possible to use such a model as a prior in a Bayesian method in conjunction with rNNI or rSPR moves, while keeping the search space connected.

Preliminaries
In this section, we define phylogenetic networks and recall the original definition of orchard networks. Then we recall the definition of an rNNI move on a phylogenetic network, and some results related to these moves.
Definition 1. A directed phylogenetic network on a set of taxa X is a directed acyclic graph whose nodes are of the following types: Root a node with indegree-0 and outdegree-1.
Tree node a node with indegree-1 and outdegree at least 2.
Reticulation a node with indegree at least 2 and outdegree-1.
The leaves are bijectively labelled by the taxa in X. Because of this, we will refer to a leaf l by its label in X and vice versa. Non-leaf nodes will also be called internal nodes. Furthermore, we will refer to directed phylogenetic networks as networks for short.
A network where all tree nodes and reticulations have total degree (sum of indegree and outdegree) exactly 3 is called a binary network. We use the term non-binary to mean not necessarily binary; in particular, binary networks are also non-binary. Most networks we will consider in this paper are directed binary phylogenetic networks. We shall prove results on non-binary networks only in Section 3.2.
As a network N is a directed acyclic graph, we have a natural ordering on the nodes of N . If N contains an arc (u, v), then we say that u is a parent of v, that v is a child of u, that u is the tail of (u, v) and that v is the head of (u, v). If there is a directed path from u to v, then we say that u is above v and v is below u. An arc (u, v) is a reticulation arc if v is a reticulation; it is a tree arc otherwise.
The reticulation number r(N ) of a network N is the total number of reticulation arcs minus the total number of reticulation nodes in N . In a binary network, the reticulation number is simply the number of reticulation nodes.
We say that two networks N, N ′ are isomorphic if there exists a bijection f between the nodes of N and the nodes of N ′ such that (u, v) is an arc of N if and only if (f (u), f (v)) is an arc of N ′ and each labelled node of N is mapped to a node in N ′ with the same label.
Let N be a network and let v be a node in N . For an arc (u, v) in N , contracting the arc (u, v) is the action of deleting the arc (u, v) and identifying u and v. We say that a network N ′ is a binary resolution of N if N ′ is binary and a network isomorphic to N can be obtained from N ′ by contracting arcs.

Orchard networks
Orchard networks were first introduced as networks that can be reduced by picking cherries and reticulated cherries [JM21,ESS19]. In this section, we recall this definition of orchard networks.
Definition 2. An ordered pair of leaves (x, y) in a network N is a cherry if x and y share a common parent. The pair (x, y) is a reticulated cherry if the parent p x of x is a reticulation, and p x and y share a common parent. If (x, y) is a cherry or a reticulated cherry, we call it a reducible pair.
Suppressing a node v with exactly one parent u and exactly one child w refers to deleting the node v and adding an arc (u, w).
Definition 3. Let N be a non-binary network and let (x, y) be a pair of leaves in N . Let p x , p y denote the parents of x, y, respectively, and let g x denote the parent of p x that is not p y , and let g y denote a parent of p y . Reducing (or picking) the pair (x, y) in N consists of the following: • If (x, y) is a cherry, then delete x, and suppress p x if p x is consequently a node of indegree-1 and outdegree-1.
• If (x, y) is a reticulated cherry, delete the arc (p y , p x ), and suppress indegree-1 and outdegree-1 nodes (p x and p y are the only candidates for this suppression).
• If (x, y) is not a cherry nor a reticulated cherry, then do nothing.
It is easy to see that the graph obtained by reducing a pair from a network is still a network, precisely because we suppress indegree-1 and outdegree-1 nodes. We denote the network obtained by reducing a pair (x, y) from a network N by N (x, y). Let S be a sequence of ordered pairs on distinct elements. The network obtained by repeatedly reducing the pairs of S in order from N is denoted N S.

Definition 4.
A network is orchard if there exists a sequence of ordered pairs S such that N S is a tree with one leaf. In such a case, we say that S reduces N .
We call a sequence of ordered pairs a cherry-picking sequence if it reduces some orchard network, such that the length of the sequence is minimal. It was shown independently in [JM21,ESS19] that picking any reducible pair in an orchard network results in another orchard network (also for non-binary networks [JM21]). This means that in general, orchard networks may have multiple cherry-picking sequences that reduce them. See Figure 1 for an example of an orchard network.

Tree-based networks
Tree-based networks were introduced as those that can be obtained by adding arcs between arcs of a given base tree [FS15]. We recall the following definition.
Definition 5. A binary network N is tree-based with base tree T if N can be obtained from T in the following steps: 1. Replace some arcs of T by paths, whose internal nodes are called attachment points; each attachment point is of indegree-1 and outdegree-1; 2. Place arcs between attachment points, called linking arcs, so that the graph contains no nodes of total degree greater than 3, and so that it remains acyclic; and 3. Suppress all attachment points not incident to any linking arcs.
Definitions regarding rearrangement moves are given in Section 4.1.

Characterization of orchard networks
In this section, we prove that orchard networks can be characterized as phylogenetic networks that admit a certain type of time-consistent labelling. We show this first for binary orchard networks, and later extend the characterization to non-binary orchard networks.

Binary orchard networks
Definition 6. Let N be a binary phylogenetic network with node set V . An HGT-consistent labelling of N is a labelling t : V → R such that 3. For each reticulation r with parents u and v, exactly one of t(u) = t(r) and t(v) = t(r) holds.
The properties listed above in Definition 6 will be referred to as Properties 1,2, and 3, respectively. The biological interpretation of a network with an HGT-consistent labelling is that reticulations are caused within the network by horizontal transfers. Property 3 ensures that reticulation nodes are contemporaneous with one of their parents -in particular, with the parent from which genetic material is passed via the horizontal arc. Intuitively, one can view a network with an HGT-consistent labelling as a tree with horizontal arcs added to it. This means that a base tree of a given network with HGT-consistent labelling can be obtained by deleting all reticulate arcs with endpoints of the same label (horizontal arcs). The following observation follows immediately.
Observation 1. Each binary network that admits an HGT-consistent labelling is tree-based. In particular, a base tree can be obtained by deleting all reticulation arcs where the tail and head have the same time labels.
The converse of Observation 1 does not hold. This can be seen as follows. We say that a network contains a crown if there exists a set of nodes {u 1 , . . . , where the indices are taken modulo k. Consider a tree-based network that contains a crown, such as the network in Figure 2. Such a network does not admit an HGT-consistent labelling. To see this, first note that in such a labelling t, without loss of generality, We now show that every binary orchard network admits an HGT-consistent labelling of a certain form.
Lemma 1. Each binary orchard network admits an HGT-consistent labelling t where two nodes have the same label only if they are a parent-child pair where the parent is a tree node and the child a reticulation.
Proof. Let N be a binary orchard network with leaves l 1 , . . . , l n , and let S = (x 1 , y 1 ), . . . , (x m , y m ) be a cherrypicking sequence for N . Because N is binary, it can be reconstructed from S by starting with the one-leaf tree with leaf y m and reattaching the pairs from S in reverse order 1 . Now label the root node ρ with t(ρ) = 0, each leaf l j with t(l) = m + j, and each internal node v added when reattaching the pair ( We show that t is indeed an HGT-consistent labelling of N . When adding a pair to a network, the two newly introduced nodes are not above any existing internal nodes, and have a greater time labelling than any Figure 2: A binary tree-based network N on the taxa set {a, b} that does not admit an HGT-consistent labelling since it contains a crown on the nodes u 1 , u 2 , v 1 , v 2 . other existing internal nodes. Thus any internal node has time label greater than or equal to that of any of its parents. Adding to the fact that we label the leaves so that they have labels of at least m + 1 and internal nodes have labels of at most m, we have that for all arcs (u, v), t(u) ≤ t(v). The labelling of the leaves also means that two nodes in the network have the same label under t only if they are a parent-child pair where the parent is a tree node and the child is a reticulation. Therefore, Property 1 of the HGT-consistent labelling is satisfied. To see that t satisfies Property 2, we look at tree nodes and reticulations separately. A tree node u has two children, one of which is possibly added to the network at the same time as u. The other child v of u is either a leaf or an internal node that is added to the network after u has been added. But this would mean that t(u) < t(v). On the other hand, a reticulation r has one child c. Every reticulation node is added to the network with one of its (non-reticulation) parents; this means that c is either a leaf or an internal node that is added to the network after r has been added. This implies t(r) < t(c). So Property 2 is satisfied. Finally, to see that Property 3 is also satisfied, consider a reticulation r with parents u and v. The reticulation r must have been added to the network with one of its parents, say u, so that t(u) = t(r). This means that the node v was already in the network when r was added; due to how we have defined t, we must have that t(v) < t(r). Thus t satisfies Property 3, and therefore it is an HGT-consistent labelling.
In addition, this gives a labelling t in which each label is used at most twice. Indeed for each i ∈ {1, . . . , m}, the nodes with label i are added to the network when (x i , y i ) is reattached, and for each such reattachment, at most two nodes are added to the network. Observe that under this construction, if two nodes have the same label, then they must be a parent-child pair where the parent is a tree node and the child a reticulation.

Lemma 2. Each binary network that admits an HGT-consistent labelling is orchard.
Proof. Suppose a binary network N admits an HGT-consistent labelling t. We will prove that N is orchard by proving that each network that admits an HGT-consistent labelling which has at least one internal node must contain a cherry or reticulated cherry. Moreover, after reducing such a pair, the resulting network still admits an HGT-consistent labelling. Therefore, any HGT-consistent network can be reduced to a tree with one leaf, and is thus orchard.
Let x be an internal node with t(x) maximal. If x is a reticulation, then its child l must be a leaf, and one of its parents p has label t(p) = t(x), by Property 3. The node p cannot be a reticulation as this would contradict Property 2 of HGT-consistent labellings. Hence, the other child l ′ of p must be a leaf as well, and the reducible pair (l, l ′ ) is a reticulated cherry in N . Reducing this reticulated cherry, we obtain a new network N ′ , which still admits an HGT-consistent labelling t ′ = t| V (N ′ ) . If x is a tree node, then either both of its children are reticulations, one of its children v is a reticulation node, or both its children are leaves. In the first case, the reticulation children v 1 and v 2 must have labels t(v 1 ) = t(v 2 ) = t(x), since x has the greatest time label out of internal nodes and internal nodes have time label greater than or equal to that of their parents, by Property 1. But this contradicts Property 2, so this case is not possible. In the second case, the reticulation child has label t(v) = t(x), and we can reduce the reticulated cherry involving x and v as in the previous case. In the third case, x has two leaf children, which must thus form a cherry. After reducing this cherry, the network still admits an HGT-consistent labelling, which can be obtained by restricting t to the remaining nodes.
A direct consequence of these lemmas is the following new characterization of orchard networks as networks that admit an HGT-consistent labelling.

Theorem 1. A binary network N is orchard if and only if it admits an HGT-consistent labelling.
The next corollary, which was also shown in [HvIJ + 19, vIJJ + 21b], follows from Observation 1 and Theorem 1. This means in particular that orchard networks have a base tree.  Figure 3: A non-binary orchard network on {a, b} that does not admit a time-labelling on the nodes that adheres to the 'reticulations have the same labels as all but one of its parents' rule. Indeed, under this rule, exactly two of t 1 , t 2 , t 3 must have the same time-label, but no labelling can satisfy this rule. Therefore, this labelling rule does not fully characterize the class of non-binary orchard networks.

Non-binary orchard networks
By recalling a key lemma from [vIJJ + 21b] regarding non-binary orchard networks and their binary resolutions, we extend the HGT-consistent labelling characteristics to non-binary orchard networks. Proof. The combination of Theorem 1 and Lemma 3 immediately gives the claim.
Ideally, we would like to extend this characterization by finding a direct time labelling of non-binary networks that captures orchard networks, with a meaningful biological interpretation. A natural generalization would be to consider a labelling where every reticulation is contemporaneous with all but one parent in the network. This implies the existence of a base tree, for which all arcs that are not in the base tree are horizontal arcs. Unfortunately, this characterization does not fully capture the class of non-binary orchard networks. Figure 3 gives an example of a non-binary orchard network that does not admit a labelling under this property.

Orchard network space
We prove that the space of binary orchard networks is connected using a strategy that is reminiscent of the proofs of connectedness in [Jan21] for local head moves and in [EFM21] for tree-based networks. We first move all reticulations to the top of the network and then change the pendant trees below these reticulations. Before we prove connectedness, we will first give the formal definitions and introduce some structures and subgraphs we use in the proofs.

Rearrangement moves
We start by defining rSPR and rNNI moves on phylogenetic networks. Intuitively, rSPR moves can be seen as moving either the head or the tail of an arc and rNNI moves are local rSPR moves.
Definition 7. (See Figure 4) Let N be a binary network with an arc (z, w) and an arc e with endpoints x and y (either e = (x, y) or e = (y, x)), and let p and c be, respectively, the parent and child of x that are not y. The rSPR move (p, x, c) e − → (z, w) consists of the following: replace the arcs (p, x), (x, c), and (z, w) with the arcs (p, c), (z, x), and (x, w). If {p, c} ∩ {z, w} = ∅, then the move is an rNNI move.
An rSPR (or rNNI) move is valid if the resulting graph is a network. We first show that this holds automatically for orchard networks if the resulting graph has an HGT-consistent labelling. For that, we need to define HGT-consistent labellings on more general directed graphs. Note that the following definition is equivalent to Definition 6 if D is a network.
Definition 8. Let D = (V, A) be a directed graph that may contain parallel arcs, with indegree and outdegree at most 2 and total degree at most 3. An HGT-consistent labelling of D is a labelling t : V → R such that: 1. For all arcs (u, v), t(u) ≤ t(v) and equality is only allowed if v has indegree 2. 2. For each node u with at least one child, there is a child v of u such that t(u) < t(v).
3. For each node r with two parents u and v, exactly one of t(u) = t(r) and t(v) = t(r) holds.
Lemma 4. Let N be a binary orchard network and N ′ the result of an rSPR move on N . If N ′ admits an HGT-consistent labelling, then N ′ is a network and hence the rSPR move is valid.
Proof. Suppose the rSPR move is (p, x, c) e − → (z, w), where e is the edge incident on x that is not incident on p nor c. Let t be an HGT-consistent labelling of N ′ .
First note that N ′ cannot contain parallel arcs say from a to b. Indeed, this would make b into a reticulation node, and one of its parents must have the same label, so t(a) = t(b). However, at least one child of a must have a larger label than a by Property 2 of Definition 8, so t(a) < t(b), a contradiction.
In addition, N ′ cannot contain a directed cycle. Suppose for a contradiction that N ′ does contain a directed cycle. Then, by Property 1 of Definition 8, all nodes in this cycle must have the same label, and they must be reticulation nodes. However, reticulation nodes only have one outgoing arc, and the head of this arc must have a strictly larger label, a contradiction. Hence, N ′ cannot contain a directed cycle.
Since N ′ does not contain parallel arcs or directed cycles, and rSPR moves do not change the degrees, if follows that N ′ is a network and hence the rSPR move is valid.
If the result of a valid rNNI move on N is a network that is isomorphic to network N ′ (respecting leaf labels), then we say that N can be transformed into N ′ using one rNNI move. It is not too difficult to observe from the definition that rNNI moves are symmetric, i.e., N can be transformed into N ′ using one rNNI move if and only if N ′ can be transformed into N using one rNNI move.
Definition 9. The rNNI space of orchard networks with n leaves and k reticulations is the graph Orch(n, k), whose nodes are binary orchard networks, and there is an edge between two networks if one can be transformed into the other in one rNNI move.

Connectedness of the rNNI space of orchard networks
In this section, we prove that Orch(n, k) is connected for all n and k. The main idea of the proof is to show that we can transform any orchard network into some canonical network in which all reticulations are stacked just below the root of the network. This is formalized as follows. See also Figure 5.
which are called the horizontal arcs at the top. In addition, there is no arc between the child of y k and the child of x k that is not y k (because otherwise N would have k + 1 reticulations at the top). The reticulations y 1 , . . . , y k are reticulations at the top. If (x i , y i ) = (a i , b i ) for all i, then we say that N has k reticulations neatly at the top.
We now show that the name "horizontal arcs at the top" is well chosen, i.e., that they are horizontal with respect to any HGT-consistent labelling.
Lemma 5. If N is a binary orchard network with k reticulations at the top, and t an HGT-consistent labelling, then for each horizontal arc at the top (x i , y i ), holds that t(x i ) = t(y i ).
Proof. The proof is by induction on i. First consider i = 1. Since y 1 is a reticulation, we have, by the definition of HGT-consistent labelling, that either t(y 1 ) = t(x 1 ) or t(y 1 ) = t(v ρ ). We have t(y 1 ) ≥ t(x 1 ) because (x 1 , y 1 ) is an arc. Furthermore, t(x 1 ) > t(v ρ ) because x 1 is not a reticulation. Hence, we have t(y 1 ) ≥ t(x 1 ) > t(v ρ ). So t(y 1 ) = t(v ρ ) is not possible and we must have t(y 1 ) = t(x 1 ).  rNNI move (b 3 , a 3 , b 4 ) a 4 ) to N ′ . The highest three horizontal arcs at the top are reoriented. The network N ′′ has four reticulations neatly at the top. Now assume that t(x i ) = t(y i ). We will show that t(x i+1 ) = t(y i+1 ). First note that we do not know whether x i is a parent of x i+1 and y i of y i+1 or if x i is a parent of y i+1 and y i of x i+1 , but this does not matter for the proof since t(x i ) = t(y i ). Since y i+1 is a reticulation, we have that either t(y i+1 is not possible and we must have t(y i+1 ) = t(x i+1 ).
Reorienting an arc (u, v) of a network N refers to modifying N into a network N ′ that is isomorphic to N with (u, v) replaced by (v, u). Note that reorienting any subset of the horizontal arcs at the top of a binary orchard network results in a binary orchard network, as the node labelling remains HGT-consistent. The following lemma shows that, if a network has k reticulations at the top and k ′ ≤ k, then the highest k ′ horizontal arcs at the top (i.e. the arcs (x i , y i ) for i = 1, . . . , k ′ ) can be reoriented using one rNNI move, see Figure 5.
Lemma 6 (Lemma 5 of [Jan21]). Let N be a binary orchard network with k reticulations at the top and k ′ ≤ k. Then, using one rNNI move, the highest k ′ horizontal arcs at the top can be reoriented.
We will prove that we can transform any orchard network into a network in which all reticulations are at the top. We first consider the case of moving a reticulation r that is part of a triangle, i.e. when there are arcs (v, p), (v, r), and (p, r). In this case, we also say that the triangle is at v. Observe that, by the same argument as in the first part of the proof of Lemma 5, t(p) = t(r) for any HGT-consistent labelling t. The following lemma shows that such a reticulation r can either be moved up or directly to the top. Lemma 7. Let N be a binary orchard network with k < r(N ) reticulations at the top. Let t be an HGTconsistent labelling and r a reticulation not at the top minimizing t(r). Suppose that r is part of a triangle (w, p), (w, r), (p, r). Then we can either reduce the number of nodes above r by 1, in 2 rNNI moves, or transform N into an orchard network with k + 1 reticulations at the top, in at most 4 rNNI moves.
Proof. Let t be an HGT-consistent labelling for N . Let q be the parent of w. First suppose that q is not an endpoint of a horizontal arc at the top. Then q is a tree node by our choice of r. Let v be its child other than w. In that case, the graph N ′ obtained by rNNI move (q, w, p) (w,r) − −− → (q, v) admits an HGT-consistent labelling (see Figure 6) where ǫ > 0 is small enough. In particular, choose ǫ so that t ′ (q) < t ′ (w). Then, N ′ is an orchard network by Lemma 4 and Theorem 1. Let c be the child of r in N ′ , and we apply to N ′ the move (q, w, r) (w,v) −−−→ (r, c) to obtain the graph N ′′ . The graph N ′′ is an orchard network, since it admits the HGT-consistent labelling  Figure 7: The second case in the proof of Lemma 7, where q is a reticulation at the top. Three rNNI moves are applied to the orchard network, which results in an orchard network where reticulation r is also at the top. If q is not a reticulation in the original network, one extra rNNI move is applied first to make q a reticulation. Now suppose that q is an endpoint of a horizontal arc at the top. Then we can use the following rNNI moves to move (p, r) to the top. First, if q is not a reticulation, reorient the reticulation arc leaving q so that q becomes a reticulation, using one rNNI move (Lemma 6). Let s be the parent of q with t(q) = t(s), let v be the child of s that is not q and let c be the child of r (see Figure 7). Apply the following three moves: c). To see that the graphs after the three moves are orchard networks, note that the following are HGT-consistent labellings of the respective resulting graphs: where 0 < γ < δ < ǫ are very small. Observe that reticulation r is now at the top and (p, r) a horizontal arc at the top (see Figure 7). Hence, the resulting graph obtained using at most 4 rNNI moves, is an orchard network with k + 1 reticulations at the top.
We are now ready to prove that we can move all reticulations to the top. Lemma 8. Let N be a binary orchard network with k < r(N ) reticulations at the top and n leaves. Then, using at most 2n rNNI moves, N can be transformed into a binary orchard network with k + 1 reticulations at the top.
Proof. Let N be an orchard network with HGT-consistent labelling t such that two nodes have the same label only if they are a parent-child pair for which the parent is a tree node and the child a reticulation (which exists by Lemma 1). Let r be a reticulation not at the top minimizing t(r). Let p be the parent of r with t(r) = t(p) and u the other parent of r. Observe that, since t(r) = t(p), p must have a second child with larger label. Hence, p cannot be a reticulation. Let q be the parent of p. In addition, let y be a lowest common ancestor (LCA) of u and q in N .  Figure 8: Illustration of the proof of Lemma 8 for the case t(u) > t(q). (a) When u is a tree node, the head of the reticulation arc (p, r) is moved up. (b) When u is a reticulation at the top, an LCA y of u and q is a parent of u with t(y) = t(u), leading to a contradiction to the assumption t(u) > t(q).
First suppose t(u) > t(q) (and hence u = q). Note that u is either a tree node or a reticulation at the top, by the choice of r. If u is a tree node, we can apply the move (u, r, c) (p,r) − −− → (s, u) where s is the parent of u, v is the child of u other than r, and c is the child of r (Figure 8). Then with ǫ > 0 small enough, is an HGT labelling of the resulting network, which is therefore an orchard network by Lemma 4. In the resulting network, the number of nodes above r is reduced by 1.
If u is a reticulation at the top, then y is the parent of u with t(y) = t(u). However, because y is above q, we have t(y) ≤ t(q) and so t(u) ≤ t(q), contradicting our assumption t(u) > t(q).
The case that t(u) < t(q) is symmetric. We can argue as in the previous paragraph but replacing u, r by q, p respectively, see Figure 9.
The last case is that t(u) = t(q). We claim that u = q = y. Otherwise, by our choice of the labelling t, we either have an arc (q, u) and u is a reticulation, or we have an arc (u, q) and q is a reticulation. In the first scenario, u must be a reticulation at the top by our choice of r. However, since r is a child of u and p a child of q, it follows that r is also a reticulation at the top, a contradiction. In the second scenario, q must be a reticulation at the top and we again obtain a contradiction, by the same reasoning. Therefore, we conclude that u = q = y. This means that there is a triangle (y, r), (y, p), (p, r) and we can apply Lemma 7 to either increase the number of reticulations at the top by 1 in at most 4 rNNI moves, or reduce the number of nodes above r by 1 in 2 rNNI moves.
It remains to bound the number of moves. We say that a node is a base node if it is an internal node of the base tree obtained by deleting all arcs (u, v) with t(u) = t(v) and suppressing indegree-1 outdegree-1 nodes. Hence, an internal node is a base node precisely if it has no parent or child with the same label in the HGT-consistent labelling t. Define a b (v) as the number of base nodes above v. Hence, a reticulation r is at the top if and only if a b (r) = 2. Since a rooted phylogenetic tree with n leaves has n internal nodes, the network N has n base nodes.
In the proof above, we consider a reticulation r not at the top minimizing t(r). Consequently, all nodes above r are base nodes or endpoints of horizontal arcs at the top. If r is not part of a triangle, we reduce the number of nodes above r, and hence a b (r), by 1 in one rNNI move. If r is part of a triangle, we achieve the same in 2 rNNI moves, or move r to the top in at most 4 rNNI moves. We end with a b (r) = 2. Hence, we need at most 2 rNNI moves per base node, except the root and its child, plus at most 4 additional moves. The total number of rNNI moves required to move r to the top is at most 2(n − 2) + 4 = 2n. The next step is to move all but one of the leaves to one side of the network, see Figure 10. Proof. Let (x, y) be the lowest horizontal arc at the top. Let u 0 be the child of x other than y. Let y, u 1 , . . . , u m = l be the unique directed path from y to l. Let v i be the child of u i other than u i+1 or l, for i = 1, . . . , m − 1. We apply the following sequence of rNNI moves: (y, u i , u i+1 ) (ui,vi) − −−− → (x, y) and (x, u i , y) (ui,vi) − −−− → (x, u i−1 ) for all i = 1, . . . , m−1. See Figure 11. It can easily be checked that the following maps t  Figure 9: Illustration of the proof of Lemma 8 for the case t(q) > t(u). (a) When q is a tree node, the tail of the reticulation arc (p, r) is moved up. (b) When q is a reticulation at the top, an LCA y of u and q is a parent of q with t(y) = t(q), leading to a contradiction to the assumption t(q) > t(u). labellings of the graphs obtained after the first and, respectively, second rNNI move, for i = 1, . . . , m − 1. Letting t = t (0) 2 denote an HGT-labelling for N , we have where ǫ > 0 is very small. Hence, all intermediate graphs, as well as the final one, are orchard networks. The final network (see Figure 10) still has r(N ) reticulations at the top, and l is the child of y. Moreover, as m ≤ n − 2, the sequence of moves contains at most 2(n − 2) = 2n − 4 rNNI moves.
We are now ready to prove that the space of orchard networks is connected by rNNI moves, for a fixed number of reticulations and set of taxa. We basically prove this theorem by showing that each orchard network can be transformed into one particular network (see Figure 10). This shows that, in the space of orchard networks with the same number of leaves and reticulations, there is a path from each node to one given node, and, thus, the space is connected.
Theorem 3. The space of binary orchard networks with n leaves and k reticulations is connected under rNNI moves with diameter at most 4kn + n⌈log 2 (n)⌉ + 2k + 6n − 8 which is O(kn + n log(n)).
Proof. Consider any two binary orchard networks N 1 , N 2 with k reticulations on the same set of n taxa. Fix an arbitrary leaf l. In each of the two networks, we do the following. First move all reticulations to the top using the moves in Lemma 8. For each reticulation, this takes at most 2n moves, so at most 2kn rNNI moves in Figure 11: Illustration of the rNNI moves in the proof of Lemma 9.
total. Using at most k rNNI moves, the horizontal arcs at the top can be reoriented such that the network has k reticulations neatly at the top, and such that l is below the head of the lowest horizontal arc at the top, by Lemma 6. Using at most 2n − 4 moves, we can move all leaves except l below the tail x of the lowest horizontal arc at the top, by Lemma 9. This is done on both N 1 and N 2 , so the contribution towards the number of moves up until this point is 2(2kn + k + 2n − 4). Let diam rNNI (n, k) denote the diameter of Orch(n, k). Let T i denote the subtree rooted at the child of x other than y in N i (i.e. the subtree rooted at u m−1 in Figure 10). Note that T i contains all leaves except l. We can change T 1 into T 2 using at most diam rNNI (n−1, 0) ≤ 2n+n⌈log 2 (n)⌉ moves [LTZ96,EFM21]. It follows that diam rNNI (n, k) ≤ 2(2kn + k + 2n − 4) + diam rNNI (n − 1, 0) ≤ 4kn + n⌈log 2 (n)⌉ + 2k + 6n − 8 = O(kn + n log(n)) moves.

Discussion
In this paper, we have shown that binary orchard networks can be characterized as networks with an HGTconsistent labelling, meaning that they can be obtained from a tree by inserting horizontal arcs. Hence, this class of networks, which was introduced for its computational benefits, also has a biological interpretation.
This does not mean that orchard networks can only be applied in situations where reticulations represent HGT events. Although orchard networks can be drawn as HGT networks, they can also be drawn differently. Hence, orchard networks may still be useful in applications where reticulations represent hybridizations or other reticulate events. Restricting to orchard networks may exclude some scenarios in that case, but the nice mathematical properties may outweigh that, especially when they can be exploited to develop efficient algorithms.
We have also shown that non-binary orchard networks can be characterized using this time labelling on a binary refinement. However, this characterization is less satisfying as it does not specify which binary refinement to use. We leave it as an open question to find a characterization that uses a time-labelling directly on the nonbinary network.
To show the mathematical utility of the new characterization, we have used this new characterization to prove that the space of orchard networks is connected under rNNI moves. As mentioned, this may prove important, because some statistical network generators introduce reticulations as HGT events [PSC19], which naturally leads to orchard networks. Hence, if such generators are used as a prior in a Bayesian method for network inference, the prior probability of all non-orchard networks will be zero, so it is important to know that the space of orchard networks is connected.
To see whether it makes sense computationally to restrict to orchard networks, it would also be interesting to know whether our upper bound on the diameter of the space of orchard networks of order O(kn + n log n) is asymptotically tight. Indeed, smaller diameters can be favourable when deciding on a network space to search through, as it could mean a shorter mixing time for Markov Chain Monte Carlo methods [Kla20]. The bound is, in any case, close to the bound for tree-based networks (O(kn + k 2 + n log n) [EFM21]). It is clear the asymptotic bound cannot get smaller than O(n log n), as this is tight for trees, but it may be possible to remove or reduce the kn part.
Note that our results are only given for rNNI moves, and not for local tail or local head moves separately, as is done for tree-based networks in [EFM21]. It might be true that the space of orchard networks is also connected under distance-1 tail moves, or distance-2 head moves, but our proof does not imply this, as we have used a mix of distance-1 tail moves and distance-1 head moves. It would be of interest to investigate this further.