---
abstract: 'Recently, the minimum number of reticulation events that is required to simultaneously embed a collection ${{\mathcal P}}$ of rooted binary phylogenetic trees into a so-called temporal network has been characterized in terms of cherry-picking sequences. Such a sequence is a particular ordering on the leaves of the trees in ${{\mathcal P}}$. However, it is well-known that not all collections of phylogenetic trees have a cherry-picking sequence. In this paper, we show that the problem of deciding whether or not ${{\mathcal P}}$ has a cherry-picking sequence is NP-complete for when ${{\mathcal P}}$ contains at least eight rooted binary phylogenetic trees. Moreover, we use automata theory to show that the problem can be solved in polynomial time if the number of trees in ${{\mathcal P}}$ and the number of cherries in each such tree are bounded by a constant.'
address:
- 'Department of Computer Science, University of Tübingen, Germany'
- 'Department of Computer Science, University of Auckland, New Zealand'
author:
- Janosch Döcker
- Simone Linz
title: 'On the existence of a cherry-picking sequence'
---

2P2N-3-SAT,cherry,cherry-picking sequence,Intermezzo,phylogenetic tree,temporal phylogenetic network

Introduction
============

To represent evolutionary relationships among species, phylogenetic trees have long been a powerful tool. However, as we now not only acknowledge speciation but also non-tree-like processes such as hybridization and lateral gene transfer to be driving forces in the evolution of certain groups of organisms (e.g. bacteria, plants, and fish) [@mallet16; @soucy15], phylogenetic networks become more widely used to represent ancestral histories. A phylogenetic network is a generalization of a rooted phylogenetic tree. More precisely, such a network is a rooted directed acyclic graph whose leaves are labeled [@huson10].

The following optimization problem, which is biologically relevant and mathematically challenging, motivates much of the theoretical work that has been done in reconstructing phylogenetic networks from phylogenetic trees. Given a collection ${{\mathcal P}}$ of rooted binary phylogenetic trees on a set of species such that ${{\mathcal P}}$ correctly represents the tree-like evolution of different parts of the species’ genomes, what is the smallest number of reticulation events that is required to simultaneously embed the trees in ${{\mathcal P}}$ into a phylogenetic network? Here, reticulation events are collectively referring to all non-tree-like events and they are represented by vertices in a phylogenetic network whose in-degree is at least two. Without any structural constraints on a phylogenetic network, it is well-known that ${{\mathcal P}}$ can always be embedded into such a network [@baroni05; @semple07] and, hence, the optimization problem is well-defined. Moreover, despite the problem being NP-hard [@bordewich07], even for when $|{{\mathcal P}}|=2$, several exact algorithms have been developed that, given two rooted phylogenetic trees, construct a phylogenetic network whose number of reticulation events is minimized over the space of all networks that embed both trees [@albrecht12; @chen13; @piovesan12; @wu10].

Motivated by the introduction of temporal networks [@baroni06; @moret04], which are phylogenetic networks that satisfy several time constraints, Humphries et al. [@humphries13; @humphries13a] recently investigated the special case of the aforementioned optimization problem for when one is interested in minimizing the number of reticulation events over the smaller space of all temporal networks that embed a given collection of rooted binary phylogenetic trees. More precisely, in the context of their two papers, the authors considered [*temporal networks*]{} to be phylogenetic networks that satisfy the following three constraints:

(1) speciation events occur successively,

(2) reticulation events occur instantaneously, and

(3) each non-leaf vertex has a child whose in-degree is one.

The second constraint implies that the three species that are involved in a reticulation event, i.e. the new species resulting from this event and its two distinct parents, must coexist in time. Moreover, a phylogenetic network that satisfies the third constraint (but not necessarily the first two constraints) is referred to as a [*tree-child*]{} network in the literature [@cardona12]. Intuitively, if a phylogenetic network ${{\mathcal N}}$ is temporal, then one can assign a time stamp to each of its vertices such that the following holds for each edge $(u,v)$ in ${{\mathcal N}}$. If $v$ is a reticulation, then the time stamp assigned to $u$ is the same as the time stamp assigned to $v$. Otherwise, the time stamp assigned to $v$ is strictly greater than that assigned to $u$. Baroni et al. [@baroni06] showed that it can be checked in polynomial time whether or not a given phylogenetic network satisfies the first two constraints. Humphries et al. [@humphries13] have established a new characterization to compute the minimum number of reticulation events that is needed to simultaneously embed an arbitrarily large collection ${{\mathcal P}}$ of rooted binary phylogenetic trees into a temporal network. This characterization, which is formally defined in Section \[sec:prelim\], is in terms of [*cherries*]{}, and the existence of a particular type of sequence on the leaves of the trees, called a [*cherry-picking sequence*]{}. It was shown that such a sequence for ${{\mathcal P}}$ exists if and only if the trees in ${{\mathcal P}}$ can simultaneously be embedded into a temporal network [@humphries13 Theorem 1]. Moreover, a cherry-picking sequence for ${{\mathcal P}}$ can be exploited further to compute the minimum number of reticulation events that is needed over all temporal networks. Importantly, not every collection ${{\mathcal P}}$ is guaranteed to have a solution, i.e. there may be no cherry-picking sequence for ${{\mathcal P}}$ and, hence no temporal network that embeds all trees in ${{\mathcal P}}$. It was left as an open problem by Humphries et al. [@humphries13] to analyze the computational complexity of deciding whether or not ${{\mathcal P}}$ has a cherry-picking sequence for when $|{{\mathcal P}}|=2$.

In this paper, we make progress towards this question and show that it is NP-complete to decide if ${{\mathcal P}}$ has a cherry-picking sequence for when $|{{\mathcal P}}|\geq 8$. Translated into the language of phylogenetic networks, this result directly implies that it is computationally hard to decide if a collection of at least eight rooted binary phylogenetic trees can simultaneously be embedded into a temporal network. To establish our result, we use a reduction from a variant of the [Intermezzo]{} problem [@guttmann06]. On a more positive note, we show that deciding if ${{\mathcal P}}$ has a cherry-picking sequence can be done in polynomial time if the number of trees and the number of cherries in each such tree are bounded by a constant. To this end, we explore connections between phylogenetic trees and automata theory and show how the problem at hand can be solved by using a deterministic finite automaton.

The remainder of the paper is organized as follows. The next section contains notation and terminology that is used throughout the paper. Section \[sec:intermezzo\] establishes NP-completeness of a variant of the [Intermezzo]{} problem which is then, in turn, used in Section \[sec:cps\] to show that it is NP-complete to decide if ${{\mathcal P}}$ has a cherry-picking sequence [for when $|{{\mathcal P}}|\geq 8$]{}. In Section \[sec:cherries\], we show that deciding if ${{\mathcal P}}$ has a cherry-picking sequence is polynomial-time solvable if the number of cherries in each tree and the size of ${{\mathcal P}}$ are bounded by a constant. We finish the paper with some concluding remarks in Section \[sec:con\].

Preliminaries {#sec:prelim}
=============

This section provides notation and terminology that is used in the subsequent sections. Throughout this paper, $X$ denotes a finite set.

[**Phylogenetic trees.**]{} A [*rooted binary phylogenetic $X$-tree*]{} ${{\mathcal T}}$ is a rooted tree with leaf set $X$ and, apart from the root which has degree two, all interior vertices have degree three. Furthermore, a pair of leaves $\{a,b\}$ of ${{\mathcal T}}$ is called a [*cherry*]{} if $a$ and $b$ are leaves that are adjacent to a common vertex. Note that every rooted binary phylogenetic tree has at least one cherry. We denote by $c_{{\mathcal T}}$ the number of cherries in ${{\mathcal T}}$. We now turn to a rooted binary phylogenetic tree with exactly one cherry. More precisely, we call ${{\mathcal T}}$ a [*caterpillar*]{} if $|X|=n\geq 2$ and the elements in $X$ can be ordered, say $x_1, x_2, \ldots, x_n$, so that $\{x_1, x_2\}$ is a cherry and, if $p_i$ denotes the parent of $x_i$, then, for all $i\in \{3, 4, \ldots, n\}$, we have $(p_i, p_{i-1})$ as an edge in ${{\mathcal T}}$, in which case we denote the caterpillar by $(x_1, x_2, \ldots, x_n)$. To illustrate, Figure \[fig:caterpillar\] shows the caterpillar $(D_1,D_2,\ldots,D_{|A'|})$ with cherry $\{D_1,D_2\}$. Two rooted binary phylogenetic $X$-trees ${{\mathcal T}}$ and ${{\mathcal T}}'$ are said to be [*isomorphic*]{} if the identity map on $X$ induces a graph isomorphism on the underlying trees.

[**Subtrees.**]{} Now, let ${{\mathcal T}}$ be a rooted binary phylogenetic $X$-tree, and let $X'=\{x_1,x_2,\ldots,x_k\}$ be a subset of $X$. The minimal rooted subtree of ${{\mathcal T}}$ that connects all vertices in $X'$ is denoted by ${{\mathcal T}}(X')$. Furthermore, the rooted binary phylogenetic tree obtained from ${{\mathcal T}}(X')$ by contracting all non-root degree-$2$ vertices is the [*restriction of ${{\mathcal T}}$ to $X'$*]{} and is denoted by ${{\mathcal T}}|X'$. We also write ${{\mathcal T}}[-x_1,x_2,\ldots,x_k]$ or ${{\mathcal T}}[-X']$ for short to denote ${{\mathcal T}}|(X-X')$. For a set ${{\mathcal P}}=\{{{\mathcal T}}_1,{{\mathcal T}}_2,\ldots,{{\mathcal T}}_m\}$ of rooted binary phylogenetic $X$-trees, we write ${{\mathcal P}}|X'$ (resp. ${{\mathcal P}}[-X']$) when referring to the set $\{{{\mathcal T}}_1|X',{{\mathcal T}}_2|X',\ldots,{{\mathcal T}}_m|X'\}$ (resp. $\{{{\mathcal T}}_1[-X'],{{\mathcal T}}_2[-X'],\ldots,{{\mathcal T}}_m[-X']\}$). Lastly, a rooted binary phylogenetic tree is [*pendant*]{} in ${{\mathcal T}}$ if it can be detached from ${{\mathcal T}}$ by deleting a single edge.

[**Cherry-picking sequences.**]{} Let ${{\mathcal P}}$ be a set of rooted binary phylogenetic $X$-trees with $|X|=n$. We say that an ordering of the elements in $X$, say $(x_1,x_2,\ldots,x_n)$, is a [*cherry-picking sequence*]{} for ${{\mathcal P}}$ precisely if each $x_i$ with $i\in\{1,2,\ldots,n-1\}$ labels a leaf of a cherry in each tree that is contained in ${{\mathcal P}}[-x_1,x_2,\ldots,x_{i-1}]$. Clearly, if $|{{\mathcal P}}|=1$, then ${{\mathcal P}}$ has a cherry-picking sequence. However, if $|{{\mathcal P}}|>1$, then ${{\mathcal P}}$ may or may not have a cherry-picking sequence.

We now formally state the decision problem that this paper is centered around.

[CPS-Existence]{}\
[**Instance.**]{} A collection ${{\mathcal P}}$ of rooted binary phylogenetic $X$-trees.\
[**Question.**]{} Does there exist a cherry-picking sequence for ${{\mathcal P}}$?

The significance of [CPS-Existence]{} is the problem’s equivalence to the question whether or not all trees in ${{\mathcal P}}$ can simultaneously be embedded into a rooted phylogenetic network that satisfies the three temporal constraints as alluded to in the introduction.

[**Automata and languages.**]{} Let $\Sigma$ be an alphabet. A [*language*]{} ${{\mathcal L}}$ is a subset of all possible strings (also called [*words*]{}) whose symbols are in $\Sigma$. More precisely, ${{\mathcal L}}$ is a subset of $\Sigma^*$, where the operator $*$ is the Kleene star. A [*deterministic finite automaton*]{} (or short [*automaton*]{}) is a tuple ${{\mathcal A}}= (Q, \Sigma, \delta, q_{\text{ini}}, F)$, where

(i) $Q$ is a finite set of states,

(ii) $\Sigma$ is a finite alphabet,

(iii) $\delta \colon Q \times \Sigma \rightarrow Q$ is a transition relation,

(iv) $q_{\text{ini}}$ is the initial state, and

(v) $F \subseteq Q$ are final states.

A given automaton ${{\mathcal A}}$ [*accepts*]{} a word $w = a_1a_2\ldots a_{n}$ if and only if ${{\mathcal A}}$ is in a final state after having read all symbols from left to right, i.e. $$\delta(\ldots\delta(\delta(q_{\text{ini}},a_1),a_2),\ldots a_{n})\in F.$$ The language ${{\mathcal L}}({{\mathcal A}}) \subseteq \Sigma^*$ that is [*recognized*]{} by ${{\mathcal A}}$ is defined as the set of words that ${{\mathcal A}}$ accepts. For the automata constructed in this paper, we have $|F| = 1$ and $\delta$ being a total function that maps each pair of a state in $Q$ and a symbol in $\Sigma$ to a state in $Q$. For a detailed introduction to automata theory and languages, see the book by Hopcroft and Ullman [@hopcroft79].

A variant of the [Intermezzo]{} problem {#sec:intermezzo}
=======================================

In this section, we establish NP-completeness of a variant of the ordering problem [Intermezzo]{}. Let $A$ be a finite set, and let ${{\mathcal O}}$ be an ordering on the elements in $A$. For two elements $a$ and $b$ in $A$, we write $a<b$ precisely if $a$ precedes $b$ in ${{\mathcal O}}$. With this notation in hand, we now formally state [Intermezzo]{} which was shown to be NP-complete via reduction from [3-SAT]{} [@guttmann06 Lemma 1].

[Intermezzo]{}\
[**Instance.**]{} A finite set $A$, a collection $B$ of pairs from $A$, and a collection $C$ of pairwise-disjoint triples of distinct elements in $A$.\
[**Question.**]{} Does there exist a total linear ordering on the elements in $A$ such that $a_i<a_j$ for each $(a_i,a_j)$ in $B$, and $a_i<a_j<a_k$ or $a_j<a_k<a_i$ for each $(a_i,a_j,a_k)$ in $C$?

[**Example.**]{} Consider the following instance of [Intermezzo]{} with three pairs and two disjoint triples (when viewed as sets): $$\begin{aligned}
A &= \{a_1,\, a_2,\, a_3,\, a_4,\, a_5, a_6\}, \\
B &= \{(a_1,\, a_6),\, (a_4,\, a_1),\, (a_4,\, a_3)\}, \\
C &= \{(a_1,\,a_2,\,a_3),\,(a_4,\,a_5,\,a_6)\}.\end{aligned}$$ A total linear ordering on the elements in $A$ that satisfies all constraints defined by $B$ and $C$ is $$\mathcal{O} = (a_2,\, a_4,\, a_3,\, a_1,\, a_5,\, a_6).$$

While each element $a_i\in A$ can appear an unbounded number of times in the input of a given [Intermezzo]{} instance, this number is bounded from above by $N$ in the following [Intermezzo]{} variant.

[$N$-Disjoint-Intermezzo]{}\
[**Instance.**]{} A finite set $A$, collections $B_1,B_2,\ldots,B_N$ of pairs from $A$, and collections $C_1,C_2,\ldots,C_N$ of triples of distinct elements in $A$ such that, for each $\ell \in\{1,2,\ldots,N\}$, the elements in $B_\ell\cup C_\ell$ are pairwise disjoint.\
[**Question.**]{} Does there exist a total linear ordering on the elements in $A$ such that $$a_i<a_j\textnormal{ for each }(a_i,a_j)\in \bigcup_{1 \leq \ell \leq N} B_\ell,$$ and $$a_i<a_j<a_k \textnormal{ or } a_j<a_k<a_i\textnormal{ for each }(a_i,a_j,a_k)\in \bigcup_{1 \leq \ell \leq N} C_\ell\rm{?}$$\
Let $I$ be an instance of [$N$-Disjoint-Intermezzo]{}, and let ${{\mathcal O}}$ be an ordering on the elements of $A$ that satisfies the two ordering constraints for each pair and triple in the statement of [$N$-Disjoint-Intermezzo]{}. We say that ${{\mathcal O}}$ is an [*[$N$-Disjoint-Intermezzo]{} ordering*]{} for $I$. We next show that [$4$-Disjoint-Intermezzo]{} is NP-complete via reduction from the following restricted version of [3-SAT]{}.

[2P2N-3-SAT]{}\
[**Instance.**]{} A set $U$ of variables, and a set ${{\mathcal C}}$ of clauses, where each clause is a disjunction of exactly three literals, such that each variable appears negated exactly twice and unnegated exactly twice in ${{\mathcal C}}$.\
[**Question.**]{} Does there exist a truth assignment for $U$ that satisfies each clause in ${{\mathcal C}}$?

Berman et al. [@berman03 Theorem 1] established NP-completeness for [2P2N-3-SAT]{}.

\[t:4-DI\] [4-Disjoint-Intermezzo]{} is [*NP*]{}-complete.

We show that the construction by Guttmann and Maucher [@guttmann06 Lemma 1], that was used to show that [Intermezzo]{} is NP-complete via reduction from [3-SAT]{}, yields an instance of [4-Disjoint-Intermezzo]{} if we reduce from [2P2N-3-SAT]{}. Using the same notation as Guttmann and Maucher [@guttmann06 Lemma 1], their construction is as follows. Let $I$ be an instance of [2P2N-3-SAT]{} that is given by a set of variables $U = \{u_1,\,\ldots,\,u_n\}$ and a set of clauses $${{\mathcal C}}=\{(c_{1,1} \vee c_{1,2} \vee c_{1,3}),\,\ldots,\,(c_{m,1} \vee c_{m,2} \vee c_{m,3})\},$$ where each $c_{i,j} \in \{u_1, \bar{u}_1,u_2, \bar{u}_2,\ldots,u_n, \bar{u}_n\}$. Furthermore, for $a,b\in\mathbb{N}$, let $a \oplus b$ denote the number $c \in \{1,\,2,\,3\}$ such that $a + b \equiv c \pmod 3$. We define the following three sets: $$\begin{aligned}
A &= \{u_{k,l},\,\bar{u}_{k,l} \mid 1 \leq k \leq n \wedge 1 \leq l \leq 3\} \cup {}\\
  &\hphantom{{} = {}}\{c_{i,j}^l \mid 1 \leq i \leq m \wedge 1 \leq j \leq 3 \wedge 1 \leq l \leq 3\},\\[5pt]
B &= \{(u_{k,1},\,\bar{u}_{k,3}),\,(\bar{u}_{k,1},\,u_{k,3}) \mid 1 \leq k \leq n\} \cup {}\\
  &\hphantom{{} = {}}\{(c_{i,j,2},\,c_{i,j}^{1}),\,(c_{i,j}^2,\,c_{i,j,1}) \mid 1 \leq i \leq m \wedge 1 \leq j \leq 3\} \cup {}\\
&\hphantom{{} = {}}\{(c_{i,j \oplus 1}^1,\,c_{i,j}^3) \mid 1 \leq i \leq m \wedge 1 \leq j \leq 3\},\\[5pt]
C &= \{(u_{k,1},\,u_{k,2},\,u_{k,3}),\,(\bar{u}_{k,1},\,\bar{u}_{k,2},\,\bar{u}_{k,3}) \mid 1 \leq k \leq n\} \cup {}\\
  &\hphantom{{} = {}}\{(c_{i,j}^1,\,c_{i,j}^2,\,c_{i,j}^3) \mid 1 \leq i \leq m \wedge 1 \leq j \leq 3\},\end{aligned}$$ where $c_{i,j,l}$ is an abbreviation of $u_{k,l}$ with $u_k = c_{i,j}$. By construction, the elements in $C$ are pairwise-disjoint triples of distinct elements in $A$ and, so, the three sets $A$, $B$, and $C$ form an instance of [Intermezzo]{}.

Now, we show how the pairs and triples in $B \cup C$ can be partitioned into sets $B_\ell \cup C_\ell$ with $B_\ell \subseteq
B$, $C_\ell \subseteq C$, and $1 \leq \ell \leq 4$ such that the elements in $B_\ell\cup C_\ell$ are pairwise disjoint. Recalling that $C$ is a set of pairwise-disjoint triples, we start by setting $B_1 = \emptyset$ and $C_1 = C$. Furthermore, we set $$\begin{aligned}
B_2 &= \{(u_{k,1},\,\bar{u}_{k,3}),\,(\bar{u}_{k,1},\,u_{k,3}) \mid 1 \leq k \leq n\} \cup {}\\
&\hphantom{{} = {}}\{(c_{i,j \oplus 1}^1,\,c_{i,j}^3) \mid 1 \leq i \leq m \wedge 1 \leq j \leq 3\}\end{aligned}$$ and $C_2 = \emptyset$. By construction, it is easy to check that the pairs in $B_2$ are pairwise disjoint. Lastly, consider the remaining pairs $$B \setminus B_2 = \{(c_{i,j,2}, c_{i,j}^1), (c_{i,j}^2, c_{i,j,1}) \mid 1 \leq i \leq m \wedge 1 \leq j \leq 3\}$$ and observe that the only possibility for two pairs in $B \setminus B_2$ to have a non-empty intersection is to have an element $c_{i,j,l}$ with $l\in\{1,2\}$ in common. Now, since each $c_{i,j,l}$ is equal to an element in $$U'=\{u_{k,l}, \bar{u}_{k,l}\mid 1 \leq k \leq n\wedge 1 \leq l \leq 3\},$$ and each element $u_k$ appears exactly twice negated and twice unnegated in ${{\mathcal C}}$, it follows that there is a partition of $B\setminus B_2$ into $B_3$ and $B_4$ so that all pairs in the resulting two sets are pairwise disjoint. Setting $C_3 = C_4 = \emptyset$ completes the construction of an instance of [4-Disjoint-Intermezzo]{}. Noting that it is straightforward to compute the partition $$B \cup C = \bigcup_{1 \leq \ell \leq 4} \left ( B_\ell \cup C_\ell \right )$$ in polynomial time and that we did not modify the construction described by Guttmann and Maucher [@guttmann06 Lemma 1] itself, it follows from the same proof that $I$ has a satisfying truth assignment if and only if $\bigcup_{1 \leq \ell \leq 4} \left ( B_\ell \cup C_\ell \right )$ has a [4-Disjoint-Intermezzo]{} ordering.

[**Remark.**]{} By the construction of an instance of [4-Disjoint-Intermezzo]{} in the proof of Theorem \[t:4-DI\], we note that no pair or triple occurs twice and that, for each $\ell\in\{1,2,3,4\}$, we have $B_\ell\cup C_\ell\ne\emptyset$. We will freely use these facts throughout the remainder of the paper.

Hardness of [CPS-Existence]{} {#sec:cps}
=============================

In this section, we show that the decision problem [CPS-Existence]{} is NP-complete for any collection of rooted binary phylogenetic trees on the same leaf set that consists of a constant number $m$ of trees with $m\geq 8$. To establish the result, we use a reduction from [4-Disjoint-Intermezzo]{}.

![A caterpillar on $|A'|$ leaves and with cherry $\{D_1,D_2\}$.[]{data-label="fig:caterpillar"}](CaterpillarSkeleton){width=".35\textwidth"}

Let $I$ be an instance of [4-Disjoint-Intermezzo]{}. Using the same notation as in the definition of [$N$-Disjoint-Intermezzo]{}, let $$A'=A\cup\left\{c_r^1,c_r^2,c_r^3,c_r^4\mid c_r\in\bigcup_{1 \leq \ell \leq 4} C_\ell\right\},$$ and let $D=\{d_1,d_2,\ldots,d_{|A'|}\}$. For each $\ell\in\{1,2,3,4\}$, we next construct two rooted binary phylogenetic trees. Let $A_\ell$ be the subset of $A'$ that precisely contains each element of $A'$ that is neither contained in an element of $B_\ell$ nor contained in an element of $$C_\ell\cup \{c_r^1,c_r^2,\ldots,c_r^4 \mid c_r\in C_\ell\}.$$ Furthermore, let ${{\mathcal S}}_\ell$ and ${{\mathcal S}}_\ell'$ both be the caterpillar shown in Figure \[fig:caterpillar\]. Setting $q=1$, let ${{\mathcal T}}_\ell$ and ${{\mathcal T}}_\ell'$ be the two rooted binary phylogenetic trees obtained from ${{\mathcal S}}_\ell$ and ${{\mathcal S}}_\ell'$ that result from the following four-step process.

(i) For each $(a_i,a_j)\in B_\ell$ in turn, replace the leaf $D_q$ in ${{\mathcal S}}_\ell$ (resp. ${{\mathcal S}}_\ell'$) with the 3-taxon tree on the top left (resp. bottom left) in Figure \[fig:gadgets\] and increment $q$ by one.

(ii) For each $c_r\in C_\ell$ with $c_r=(a_i,a_j,a_k)$ in turn, replace the leaf $D_q$ in ${{\mathcal S}}_\ell$ (resp. ${{\mathcal S}}_\ell'$) with the 8-taxon tree on the top right (resp. bottom right) in Figure \[fig:gadgets\] and increment $q$ by one.

(iii) For each $a_i\in A_\ell$ in turn, replace the leaf $D_q$ in ${{\mathcal S}}_\ell$ and ${{\mathcal S}}_\ell'$ with the cherry $\{a_i,d_q\}$ and increment $q$ by one.

(iv) For each element in $\{q,q+1,\ldots,|A'|\}$, replace the leaf label $D_q$ in ${{\mathcal S}}_\ell$ and ${{\mathcal S}}_\ell'$ with $d_q$.

![Gadgets for a pair $(a_i,a_j)$ (left) and gadgets for a triple $(a_i,a_j,a_k)$ (right) that are used in the reduction from [4-Disjoint-Intermezzo]{} to [CPS-Existence]{}.[]{data-label="fig:gadgets"}](gadgets){width=".6\textwidth"}

We call ${{\mathcal P}}_I=\{{{\mathcal T}}_\ell,{{\mathcal T}}_\ell' \mid 1 \leq \ell \leq 4\}$ the set of [*intermezzo trees*]{} associated with $I$. The next observation is an immediate consequence from the above construction and the fact that, for each $1 \leq \ell \leq 4$, the elements in $B_\ell$ and $C_\ell$ are pairwise disjoint.

For an instance $I$ of [4-Disjoint-Intermezzo]{}, the set of intermezzo trees associated with $I$ consists of eight pairwise non-isomorphic rooted binary phylogenetic trees whose set of leaves is $A'\cup D$.

We now establish the main result of this section.

\[lem:CPS-Existence\] Let ${{\mathcal P}}=\{{{\mathcal T}}_1,{{\mathcal T}}_2,\ldots,{{\mathcal T}}_m\}$ be a collection of rooted binary phylogenetic $X$-trees. [CPS-Existence]{} is [NP]{}-complete for $m=8$.

Clearly, [CPS-Existence]{} for $m=8$ is in NP because, given an ordering ${{\mathcal O}}$ on the elements in $X$, we can decide in polynomial time if ${{\mathcal O}}$ is a cherry-picking sequence for ${{\mathcal P}}$. Let $I$ be an instance of [4-Disjoint-Intermezzo]{}, and let ${{\mathcal P}}_I=\{{{\mathcal T}}_\ell,{{\mathcal T}}_\ell'\mid 1 \leq \ell \leq 4\}$ be the set of eight intermezzo trees that are associated with $I$. Note that each tree in ${{\mathcal P}}_I$ can be constructed in polynomial time and has a size that is polynomial in $|A|$. The remainder of the proof essentially consists of establishing the following claim.

[**Claim.**]{} $I$ is a ‘yes’-instance of [4-Disjoint-Intermezzo]{} if and only if ${{\mathcal P}}_I$ has a cherry-picking sequence.

First, suppose that ${{\mathcal P}}_I$ has a cherry-picking sequence. Let ${{\mathcal O}}$ be a cherry-picking sequence for ${{\mathcal P}}_I$, and let ${{\mathcal O}}'$ be the subsequence of ${{\mathcal O}}$ of length $|A|$ that contains each element in $A$. We next show that ${{\mathcal O}}'$ is a [$4$-Disjoint-Intermezzo]{} ordering for $I$. Let $(a_i,a_j)$ be an element of some $B_\ell$ with $1 \leq \ell \leq 4$, and let $d_q$, with $q\in\{1,2,\ldots,|A'|\}$, be the unique leaf label of ${{\mathcal T}}_\ell$ and ${{\mathcal T}}_\ell'$ such that $\{a_i,a_j,d_q\}$ is the leaf set of a pendant subtree of ${{\mathcal T}}_\ell$ and ${{\mathcal T}}_\ell'$. By construction of ${{\mathcal T}}_\ell$ and ${{\mathcal T}}_\ell'$, it is easily seen that $d_q$ exists and $a_i<a_j$ in ${{\mathcal O}}$. Hence, $a_i<a_j$ in ${{\mathcal O}}'$. Turning to the triples, let $c_r=(a_i,a_j,a_k)$ be an element of some $C_\ell$ with $1 \leq \ell \leq 4$, and let $d_q$, with $q\in\{1,2,\ldots,|A'|\}$, be the unique leaf label of ${{\mathcal T}}_\ell$ and ${{\mathcal T}}_\ell'$ such that $\{a_i,a_j,a_k,c_r^1,c_r^2,c_r^3,c_r^4,d_q\}$ is the leaf set of a pendant subtree of ${{\mathcal T}}_\ell$ and ${{\mathcal T}}_\ell'$. Again, by construction, $d_q$ exists. Let ${{\mathcal S}}_\ell={{\mathcal T}}_\ell|\{a_i,a_j,a_k,c_r^1,c_r^2,c_r^3,c_r^4,d_q\}$ and, similarly, let ${{\mathcal S}}_\ell'={{\mathcal T}}_\ell'|\{a_i,a_j,a_k,c_r^1,c_r^2,c_r^3,c_r^4,d_q\}$. It is straightforward to check that each cherry-picking sequence for ${{\mathcal S}}_\ell$ and ${{\mathcal S}}_\ell'$ satisfies either $$a_i<a_j<a_k,\textnormal{ or }a_j<a_k<a_i.$$ Hence, as ${{\mathcal S}}_\ell$ and ${{\mathcal S}}_\ell'$ are pendant in ${{\mathcal T}}_\ell$ and ${{\mathcal T}}_\ell'$, respectively, we have $a_i<a_j<a_k$, or $a_j<a_k<a_i$ in ${{\mathcal O}}$ and, consequently, in ${{\mathcal O}}'$. Since the above argument holds for each pair and each triple, it follows that ${{\mathcal O}}'$ is a [4-Disjoint-Intermezzo]{} ordering for $I$ and, so, $I$ is a ‘yes’-instance.

Conversely, suppose that $I$ is a ‘yes’-instance of [4-Disjoint-Intermezzo]{}. Let ${{\mathcal O}}'$ be a [4-Disjoint-Intermezzo]{} ordering on the elements of $A$. To ease reading, let $$C=\bigcup_{1 \leq \ell \leq 4}C_\ell.$$ Modify ${{\mathcal O}}'$ as follows to obtain an ordering ${{\mathcal O}}$.

(1) Concatenate ${{\mathcal O}}'$ with the sequence $(d_1,d_2,\ldots,d_{|A'|})$.

(2) For each $c_r=(a_i,a_j,a_k)$ in $C$, do one of the following two depending on the order of $a_i$, $a_j$, and $a_k$ in ${{\mathcal O}}'$. If $a_i<a_j<a_k$ in ${{\mathcal O}}'$, then replace $a_i$ with $a_i,c_r^2$ and replace $a_k$ with $a_k,c_r^3,c_r^1,c_r^4$. Otherwise, if $a_j<a_k<a_i$, replace $a_k$ with $a_k,c_r^3$ and replace $a_i$ with $a_i,c_r^2,c_r^1,c_r^4$.

Since ${{\mathcal O}}'$ is a [4-Disjoint-Intermezzo]{} ordering with $a_i<a_j<a_k$ or $a_j<a_k<a_i$ for each $(a_i,a_j,a_k)\in C$, it follows from the construction of ${{\mathcal O}}$ from ${{\mathcal O}}'$ that ${{\mathcal O}}$ is an ordering on the elements in $A'\cup D$. It remains to show that ${{\mathcal O}}$ is a cherry-picking sequence for ${{\mathcal P}}_I$. First, consider a pendant subtree with leaf set $\{a_i,a_j,d_q\}$ in ${{\mathcal T}}_\ell$ and ${{\mathcal T}}_\ell'$ for some $1 \leq \ell \leq 4$. By construction, $(a_i,a_j)$ is a pair in $B_\ell$ and, so, we have $a_i<a_j$ in ${{\mathcal O}}'$ and $a_i<a_j<d_q$ in ${{\mathcal O}}$. Second, consider a pendant subtree with leaf set $\{a_i,a_j,a_k,c_r^1,c_r^2,c_r^3,c_r^4,d_q\}$ in ${{\mathcal T}}_\ell$ and ${{\mathcal T}}_\ell'$ for some $1 \leq \ell \leq 4$. By construction, $(a_i,a_j,a_k)$ is a triple in $C_\ell$ and, so, we have either $a_i<a_j<a_k$ in ${{\mathcal O}}'$ and $$a_i<c_r^2<a_j<a_k<c_r^3<c_r^1<c_r^4<d_q$$ in ${{\mathcal O}}$, or $a_j<a_k<a_i$ in ${{\mathcal O}}'$ and $$a_j<a_k<c_r^3<a_i<c_r^2<c_r^1<c_r^4<d_q$$ in ${{\mathcal O}}$. Third, consider a pendant subtree with leaf set $\{a_i,d_q\}$ in ${{\mathcal T}}_\ell$ and ${{\mathcal T}}_\ell'$ for some $1 \leq \ell \leq 4$. By construction, we have $a_i<d_q$ in ${{\mathcal O}}$. Fourth, if $(a_i,a_j,a_k)\in C$, then, as $I$ has a [4-Disjoint-Intermezzo]{} ordering, there does not exist a pair $(a_k,a_j)$ in $B_\ell$ for some $1 \leq \ell \leq 4$. Lastly, observe that $(d_1,d_2,\ldots,d_{|A'|})$ is a suffix of ${{\mathcal O}}$ and that, for any two trees, say ${{\mathcal S}}$ and ${{\mathcal S}}'$ in ${{\mathcal P}}_I$, we have that ${{\mathcal S}}|D$ and ${{\mathcal S}}'|D$ are isomorphic. Since ${{\mathcal O}}'$ is a [4-Disjoint-Intermezzo]{} ordering, it is now straightforward to check that ${{\mathcal O}}$ is a cherry-picking sequence of ${{\mathcal P}}_I$. This establishes the proof of the claim and, thereby, the theorem.

The next corollary shows that [CPS-Existence]{} is not only NP-complete for a collection of eight rooted binary phylogenetic trees on the same leaf set, but for any such collection with a fixed number $m$ of trees with $m\geq 8$.

Let ${{\mathcal P}}=\{{{\mathcal T}}_1,{{\mathcal T}}_2,\ldots,{{\mathcal T}}_m\}$ be a collection of rooted binary phylogenetic $X$-trees. [CPS-Existence]{} is [NP]{}-complete for any fixed $m$ with $m\geq 8$.

Clearly, [CPS-Existence]{} for $m= t+8$ with $t \geq 0$ is in NP. To establish the corollary, we show how one can modify the reduction that is described prior to Theorem \[lem:CPS-Existence\] to obtain a set of $t+8$ rooted binary phylogenetic trees from an instance of [4-Disjoint-Intermezzo]{}. Let $I$ be an instance of [4-Disjoint-Intermezzo]{}. Throughout the remainder of the proof, we assume that there exists an $1 \leq \ell \leq 4$ such that $|B_\ell \cup C_\ell| > t$. Otherwise, since $t = m - 8$ and $m$ is fixed, it follows that $I$ has a constant number $c$ of pairs and triples with $c\leq 4(m-8)$ and is solvable in polynomial time.

Now, let $B_i$ and $C_i$ with $i \in \{1,\,2,\,3,\,4\}$ be a collection of pairs and triples, respectively, such that $|B_i \cup C_i| > t$. Theorem \[lem:CPS-Existence\] establishes the result for when $t=0$. We may therefore assume that $t>0$ and consider two cases. First, suppose that $t$ is even. Replace $B_i$ and $C_i$ in $I$ with a partition of $B_i \cup C_i$ into $\frac{t}{2} + 1$ sets. Each of the resulting new sets can be split naturally into a collection of pairs and a collection of triples of which at most one is empty. This results in $$\left (\frac t 2+1\right )+(4-1)=\frac t 2 +4$$ collections of pairs and triples, respectively. Now, for each $B_\ell$ and $C_\ell$ with $\ell\in\{1,2,\ldots,\frac t 2+4\}$, construct two rooted binary phylogenetic trees as described in the definition of the set of intermezzo trees associated with $I$. This yields $$2\left (\frac {t} 2 +4\right )=t+8=m$$ pairwise non-isomorphic trees. Second, suppose that $t$ is odd. Replace $B_i$ and $C_i$ in $I$ with a partition of $B_i \cup C_i$ into $\frac{t-1}{2} + 1$ sets. Additionally, add $B_*=\emptyset$ and $C_*=\emptyset$. Analogous to the first case, this results in $$\left (\frac {t-1} 2+1+1\right )+(4-1)=\frac {t-1} 2 +5$$ collections of pairs and triples, respectively. Again, for each $B_\ell$ and $C_\ell$ with $\ell\in\{1,2,\ldots,\frac {t-1} 2+5\}$ construct two rooted binary phylogenetic trees as described in the definition of the set of intermezzo trees associated with $I$. Noting that the two trees for $B_*$ and $C_*$ are isomorphic, it follows that the construction yields $$2\left (\frac {t-1} 2 +5\right )-1=\frac{2t-2}2+10-1=t+8=m$$ pairwise non-isomorphic trees. Since the proof of Theorem \[lem:CPS-Existence\] generalizes to a set of $m$ intermezzo trees, the corollary now follows for both cases.

Bounding the number of cherries {#sec:cherries}
===============================

The main result of this section is the following theorem.

\[t:cherry\] Let ${{\mathcal P}}=\{{{\mathcal T}}_1,{{\mathcal T}}_2,\ldots,{{\mathcal T}}_m\}$ be a collection of rooted binary phylogenetic $X$-trees. Let $c$ be the maximum element in $\{c_{{{\mathcal T}}_1},c_{{{\mathcal T}}_2},\ldots,c_{{{\mathcal T}}_m}\}$. Then solving [CPS-Existence]{} for ${{\mathcal P}}$ takes time $$O\left (|X|^{m(4c-2)+1} + \sum_{i=1}^m f_i(|X|, c_{{{\mathcal T}}_i})\right ),$$ where $f_i(|X|, c_{{{\mathcal T}}_i}) \in |X|^{O(c_{{{\mathcal T}}_i})}$. In particular, the running time is polynomial in $|X|$ if $c$ and $m$ are constant.

Let ${{\mathcal T}}$ be a rooted binary phylogenetic $X$-tree. We denote by ${{\mathcal C}}({{\mathcal T}})$ the recursively defined set of trees that contains ${{\mathcal T}}$ and $\emptyset$, and that satisfies the following property.

[**(P)**]{} If a tree ${{\mathcal T}}'$ is in ${{\mathcal C}}({{\mathcal T}})$ and $\{a,b\}$ is a cherry in ${{\mathcal T}}'$, then ${{\mathcal T}}'[-a]$ and ${{\mathcal T}}'[-b]$ are also contained in ${{\mathcal C}}({{\mathcal T}})$.

We refer to ${{\mathcal C}}({{\mathcal T}})$ as the [*set of cherry-picked trees*]{} of ${{\mathcal T}}$. Intuitively, ${{\mathcal C}}({{\mathcal T}})$ contains each tree that can be obtained from ${{\mathcal T}}$ by repeatedly deleting a leaf of a cherry.

To establish Theorem \[t:cherry\], we consider the set ${{\mathcal C}}({{\mathcal T}})$ of cherry-picked trees of ${{\mathcal T}}$. First, we develop a new vector representation for each tree in ${{\mathcal C}}({{\mathcal T}})$ and show that the size of ${{\mathcal C}}({{\mathcal T}})$ is at most $(|X|+1)^{O(c_{{\mathcal T}})}$. We then construct an automaton whose number of states is $|{{\mathcal C}}({{\mathcal T}})|+1$ and that recognizes whether or not a word that contains each element in $X$ precisely once is a cherry-picking sequence for ${{\mathcal T}}$. Lastly, we show how to use a product automaton construction to solve [CPS-Existence]{} for a set of rooted binary phylogenetic $X$-trees in time that is polynomial if the number of cherries and the number of trees in ${{\mathcal P}}$ is bounded by a constant.

We start with a simple lemma, which shows that deleting a leaf of a cherry never increases the number of cherries.

\[lem:cherries\] Let ${{\mathcal T}}$ be a rooted binary phylogenetic $X$-tree, and let $a$ be an element of a cherry in ${{\mathcal T}}$. Then, $$c_{{{\mathcal T}}}-c_{{{\mathcal T}}[-a]}\in\{0,1\}.$$

Let $b$ be the unique element in $X$ such that $\{a,b\}$ is a cherry in ${{\mathcal T}}$. Observe that each cherry of ${{\mathcal T}}$ other than $\{a,b\}$ is also a cherry of ${{\mathcal T}}[-a]$. Now, let $p$ be the parent of the parent of $a$ in ${{\mathcal T}}$, and let $c$ be the child of $p$ that is not the parent of $a$. If $c$ is a leaf, then it is easily checked that $\{b,c\}$ is a cherry in ${{\mathcal T}}[-a]$ and, so $c_{{{\mathcal T}}}-c_{{{\mathcal T}}[-a]}=0$. On the other hand, if $c$ is not a leaf, then $b$ is not part of a cherry in ${{\mathcal T}}[-a]$ and, so, $c_{{{\mathcal T}}}-c_{{{\mathcal T}}[-a]}=1$.

We now define a labeled tree that will play an important role throughout the remainder of this section. Let ${{\mathcal T}}$ be a rooted binary phylogenetic $X$-tree with cherries $\{\{a_1,b_1\},\{a_2,b_2\},\ldots,\{a_{c_{{\mathcal T}}},b_{c_{{\mathcal T}}}\}\}$. Obtain a tree ${{\mathcal T}}_{{\mathcal I}}$ from ${{\mathcal T}}$ as follows.

1.  Set ${{\mathcal T}}_\mathcal{I}$ to be ${{\mathcal T}}$.

2.  Delete all leaves of ${{\mathcal T}}_\mathcal{I}$ that are not part of a cherry.

3.  Suppress any resulting degree-2 vertex.

4.  If the root, say $\rho$, has degree one, delete $\rho$.

5.  For each cherry $\{a_i, b_i\}$ with $i\in\{1,2,\ldots,c_{{\mathcal T}}\}$, label the parent of $a_i$ and $b_i$ with $i$, and delete the two leaves $a_i$ and $b_i$.

6.  Bijectively label the non-leaf vertices of ${{\mathcal T}}_\mathcal{I}$ with $c_{{\mathcal T}}+1,c_{{\mathcal T}}+2,\ldots,2c_{{\mathcal T}}-1$.

We call ${{\mathcal T}}_{{\mathcal I}}$ the [*index tree*]{} of ${{\mathcal T}}$. By construction, ${{\mathcal T}}_{{\mathcal I}}$ is a labeled rooted binary tree that is unique up to relabeling the internal vertices. To illustrate, an example of the construction of an index tree is shown in Figure \[fig:index\]. The next observation follows immediately from the construction of an index tree.

Let ${{\mathcal T}}$ be a rooted binary phylogenetic tree, and let ${{\mathcal T}}_{{\mathcal I}}$ be the index tree associated with ${{\mathcal T}}$. The size of ${{\mathcal T}}_{{\mathcal I}}$ is $O(c_{{\mathcal T}})$. In particular, if the number of cherries in ${{\mathcal T}}$ is constant, the size of ${{\mathcal T}}_{{\mathcal I}}$ is $O(1)$.

![An example of the construction of an index tree. Steps (1) to (6) refer to the corresponding steps in the definition of an index tree. For simplicity, in Step (1), we have only indicated the leaf labels of leaves that are part of a cherry.[]{data-label="fig:index"}](indexTree){width="80.00000%"}

We next define a particular vector relative to a given set. Let $S$ be a finite set, let $\epsilon$ be an element that is not in $S$, and let $n$ be a non-negative integer. We call $$\begin{aligned}
v=&(&[\xi_1](x_{1}^1,x_{1}^2,\ldots,x_{1}^{q_1},\epsilon),\nonumber\\
&&[\xi_2](x_{2}^1,x_{2}^2,\ldots,x_{2}^{q_2},\epsilon),\nonumber\\
&&\vdots \nonumber\\
&&[\xi_n](x_n^1,x_n^2,\ldots,x_n^{q_n},\epsilon)\hspace{0.3cm})\nonumber\end{aligned}$$ an [*$S$-vector*]{} if each element in $S$ appears at most once in $v$, each $\xi_i$ is an element in $S\cup\{\epsilon\}$, and each $x_i^j$ is an element in $S$. Now consider the following two $S$-vectors: $$\begin{aligned}
v=&(&[\xi_1](x_{1}^1,x_{1}^2,\ldots,x_{1}^{q_1},\epsilon),\nonumber\\
&&[\xi_2](x_{2}^1,x_{2}^2,\ldots,x_{2}^{q_2},\epsilon),\nonumber\\
&&\vdots \nonumber\\
&&[\xi_n](x_n^1,x_n^2,\ldots,x_n^{q_n},\epsilon)\hspace{0.3cm})\nonumber\end{aligned}$$ and $$\begin{aligned}
v'=&(&[\psi_1](y_{1}^1,y_{1}^2,\ldots,y_{1}^{r_1},\epsilon),\nonumber\\
&&[\psi_2](y_{2}^1,y_{2}^2,\ldots,y_{2}^{r_2},\epsilon),\nonumber\\
&&\vdots \nonumber\\
&&[\psi_n](y_n^1,y_n^2,\ldots,y_n^{r_n},\epsilon)\hspace{0.3cm})\nonumber\end{aligned}$$ We say that $v'$ has the [*suffix-property*]{} relative to $v$ if, for each $s\in\{1,2,\ldots,n\}$, the vector component $[\psi_s](y_{s}^1,y_{s}^2,\ldots,y_{s}^{r_s},\epsilon)$ is equal to $[\psi_s](\epsilon)$ or satisfies each of the following equations $$y_{s}^{r_s} = x_{s}^{q_s}, \; y_{s}^{r_s-1} = x_{s}^{q_s-1}, \; \ldots, \; y_{s}^{1} =  x_{s}^{q_s-r_s+1}.$$ Lastly, if $v'$ has the property that $[\psi_i](y_{i}^1,y_{i}^2,\ldots,y_{i}^{r_i},\epsilon)=[\epsilon](\epsilon)$ for each $i\in\{1,2,\ldots,n\}$, we call $v'$ the [*empty vector*]{}. Note that the empty vector satisfies the suffix-property relative to every $S$-vector.

Building on the definition of an $S$-vector, we now describe a vector representation of a rooted binary phylogenetic tree that can be constructed by using its index tree as a guide. Roughly, the representation associates a caterpillar-type structure to each vertex in the index tree. Let ${{\mathcal T}}$ be a rooted binary phylogenetic $X$-tree, let $X'\subseteq X$, and let $\epsilon\notin X$. For two vertices $u$ and $v$ in ${{\mathcal T}}$, we say that $u$ (resp. $v$) is an [*ancestor*]{} (resp. [*descendant*]{}) of $v$ (resp. $u$) if there is a directed path from $u$ to $v$ in ${{\mathcal T}}$. Throughout this section, we regard a vertex $v$ of ${{\mathcal T}}$ to be an ancestor and a descendant of itself. The [*most recent common ancestor*]{} of $X'$ is the vertex $v$ in ${{\mathcal T}}$ whose set of descendants contains $X'$ and no descendant of $v$, except $v$ itself, has this property. We denote $v$ by ${{\rm mrca}}_{{{\mathcal T}}}(X')$. Now, let $\{\{a_1,b_1\},\{a_2,b_2\},\ldots,\{a_{c_{{\mathcal T}}},b_{c_{{\mathcal T}}}\}\}$ be the set of all cherries in ${{\mathcal T}}$. First, for each leaf $i\in\{1,2,\ldots,c_{{\mathcal T}}\}$ in ${{\mathcal T}}_{{\mathcal I}}$, let $(a_i,x_{i}^1,x_{i}^2,\ldots,x_{i}^q)$ be the maximal pendant caterpillar in ${{\mathcal T}}$ with cherry $\{a_i,b_i\}$. We denote this by $$[\xi_i](x_{i}^1,x_{i}^2,\ldots,x_{i}^q,\epsilon),$$ where $\xi_i=a_i$ and $x_{i}^1=b_i$. Second, for each non-leaf vertex labeled $i$ in ${{\mathcal T}}_{{\mathcal I}}$ with $i\in\{c_{{\mathcal T}}+1,c_{{\mathcal T}}+2,\ldots,2c_{{\mathcal T}}-1\}$, let $v_i$ be the vertex in ${{\mathcal T}}$ such that $$v_i={\rm mrca}_{{\mathcal T}}(\{a_j,b_j\mid j \textnormal{ is a descendant of } i \textnormal{ in } {{\mathcal T}}_{{\mathcal I}}\}),$$ and let ${{\mathcal T}}_i$ be the rooted binary phylogenetic tree obtained from ${{\mathcal T}}$ by replacing the pendant subtree rooted at $v_i$ with a leaf labeled $v_i$. Now, if $v_i$ is a leaf of a cherry in ${{\mathcal T}}_i$, let $(v_i,x_{i}^1,x_{i}^2,\ldots,x_{i}^q)$ be the maximal pendant caterpillar in ${{\mathcal T}}_i$ with cherry $\{v_i,x_{i}^1\}$. We denote this by $$[\epsilon](x_{i}^1,x_{i}^2,\ldots,x_{i}^q,\epsilon).$$ Otherwise, if $v_i$ is not a leaf of a cherry in ${{\mathcal T}}_i$, we denote this by $$[\epsilon](\epsilon).$$ Now, recall that $2c_{{\mathcal T}}-1$ is the number of vertices in ${{\mathcal T}}_{{\mathcal I}}$. Setting $n=2c_{{\mathcal T}}-1$, we call $$\begin{aligned}
v_{{\mathcal T}}=&(&[\xi_1](x_{1}^1,x_{1}^2,\ldots,x_{1}^{q_1},\epsilon),\nonumber\\
&&[\xi_2](x_{2}^1,x_{2}^2,\ldots,x_{2}^{q_2},\epsilon),\nonumber\\
&&\vdots\nonumber\\
&&[\xi_{n}](x_{n}^1,x_{n}^2,\ldots,x_{n}^{q_{n}},\epsilon)\hspace{0.3cm})\nonumber
$$ the [*vector representation of ${{\mathcal T}}$ relative to ${{\mathcal T}}_{{\mathcal I}}$*]{}, and note that $$\xi_{c_{{\mathcal T}}+1}=\xi_{c_{{\mathcal T}}+2}=\cdots=\xi_{2c_{{\mathcal T}}-2}=\xi_{n}=\epsilon.$$ An example of a tree and its vector representation is shown in Figure \[fig:vector\].

![A rooted binary phylogenetic tree ${{\mathcal T}}$ whose index tree ${{\mathcal T}}_{{\mathcal I}}$ is shown in Step (6) of Figure \[fig:index\]. The vector representation of ${{\mathcal T}}$ relative to ${{\mathcal T}}_{{\mathcal I}}$ is $([x_1](x_2,x_3,\epsilon),[x_6],(x_7,\epsilon),[x_9](x_{10},x_8,\epsilon),[\epsilon](x_5,x_4,\epsilon),[\epsilon](x_{11}, x_{12},\epsilon))$.[]{data-label="fig:vector"}](vector){width="35.00000%"}

Let ${{\mathcal T}}$ be a rooted binary phylogenetic $X$-tree with $\epsilon\notin X$, and let ${{\mathcal T}}_{{\mathcal I}}$ be the index tree of ${{\mathcal T}}$. Let $v_{{\mathcal T}}$ be the vector representation relative to ${{\mathcal T}}_{{\mathcal I}}$. Furthermore, let ${{\mathcal T}}'$ be an element in ${{\mathcal C}}({{\mathcal T}})$, and let $$\begin{aligned}
v_{{{\mathcal T}}'}=&(&[\psi_1](y_{1}^1,y_{1}^2,\ldots,y_{1}^{r_1},\epsilon),\nonumber\\
&&[\psi_2](y_{2}^1,y_{2}^2,\ldots,y_{2}^{r_2},\epsilon),\nonumber\\
&&\vdots \nonumber\\
&&[\psi_n](y_n^1,y_n^2,\ldots,y_n^{r_n},\epsilon)\hspace{0.3cm})\nonumber\end{aligned}$$ be an $X$-vector for ${{\mathcal T}}'$. We say that $v_{{{\mathcal T}}'}$ has the [*cherry-property relative to $v_{{\mathcal T}}$*]{} if, for each cherry $\{a,b\}$ in ${{\mathcal T}}'$, exactly one of the following conditions holds:

(i) There is an index $s \in \{1,\,2,\,\ldots,\,n\}$ such that $\{\psi_s, y_{s}^1\} = \{a,b\}$.

(ii) There are two distinct indices $s,t \in \{1,\,2,\,\ldots,\,n\}$ such that $\{\psi_s, \psi_t\} = \{a,b\}$, the two corresponding vector components are $[\psi_s](\epsilon)$ and $[\psi_t](\epsilon)$, respectively, there is a vertex labeled $u$ in ${{\mathcal T}}_{{\mathcal I}}$ whose two children are labeled $s$ and $t$, and $\psi_u = \epsilon$.

To establish Theorem \[t:cherry\], we next prove three lemmas.

\[l:map\] Let ${{\mathcal T}}$ be a rooted binary phylogenetic $X$-tree, and let $v_{{\mathcal T}}$ be the vector representation of ${{\mathcal T}}$ relative to an index tree of ${{\mathcal T}}$. Then each tree ${{\mathcal T}}''$ in ${{\mathcal C}}({{\mathcal T}})$ can be mapped to an $X$-vector that satisfies the suffix-property and the cherry-property relative to $v_{{\mathcal T}}$. Moreover, the mapping is one-to-one.

Set $n=2c_{{\mathcal T}}-1$. We define a mapping $f$ from the elements in ${{\mathcal C}}({{\mathcal T}})$ into the set of all $X$-vectors that satisfy the suffix-property and the cherry-property relative to $v_{{\mathcal T}}$. First, we map ${{\mathcal T}}$ to $v_{{\mathcal T}}$ and note that $v_{{\mathcal T}}$ satisfies the suffix-property and the cherry-property relative to $v_{{\mathcal T}}$. Second, we map the element $\emptyset$ in ${{\mathcal C}}({{\mathcal T}})$ to the empty vector, say $v_\emptyset$, with $n$ vector components. Again, $v_\emptyset$ satisfies the suffix-property and the cherry-property relative to $v_{{\mathcal T}}$. Now, let ${{\mathcal T}}''$ be an element in ${{\mathcal C}}({{\mathcal T}})\setminus\{{{\mathcal T}},\emptyset\}$. Recalling the recursive definition of ${{\mathcal C}}({{\mathcal T}})$, there exists a tree ${{\mathcal T}}'$ in ${{\mathcal C}}({{\mathcal T}})$ with cherry $\{a,b\}$ such that ${{\mathcal T}}'[-a]$ is isomorphic to ${{\mathcal T}}''$. Suppose that $f$ (defined below) has already mapped ${{\mathcal T}}'$ to the $X$-vector $$\begin{aligned}
v_{{{\mathcal T}}'}=&(&[\psi_1](y_{1}^1,y_{1}^2,\ldots,y_{1}^{r_1},\epsilon),\nonumber\\
&&[\psi_2](y_{2}^1,y_{2}^2,\ldots,y_{2}^{r_2},\epsilon),\nonumber\\
&&\vdots \nonumber\\
&&[\psi_n](y_n^1,y_n^2,\ldots,y_n^{r_n},\epsilon)\hspace{0.3cm}),\nonumber\end{aligned}$$ that satisfies the suffix-property as well as the cherry-property relative to $v_{{{\mathcal T}}}$. Then $f$ maps ${{\mathcal T}}''$ to a vector that can be obtained from $v_{{{\mathcal T}}'}$ in one of the following two cases.

1.  If there is an index $s \in \{1,\,2,\,\ldots,\,n\}$ such that $\{\psi_s, y_{s}^1\} = \{a, b\}$, then $f$ maps ${{\mathcal T}}''$ to a vector $v_{{{\mathcal T}}''}$ that is obtained from $v_{{{\mathcal T}}'}$ by replacing the vector component $$[\psi_s](y_{s}^1,y_{s}^2,\ldots,y_{s}^{r_s},\epsilon) \text{ with } [b](y_{s}^2,y_{s}^3\ldots,y_{s}^{r_s},\epsilon).$$

2.  Otherwise, there are two indices $s,t \in \{1,\,2,\,\ldots,\,n\}$ with $s \neq t$ such that $\{\psi_s, \psi_t\} = \{a, b\}$, where the two corresponding components have the form $[\psi_s](\epsilon)$ and $[\psi_t](\epsilon)$, respectively. Furthermore, by construction, there is a vertex labeled $u$ in ${{\mathcal T}}_{{\mathcal I}}$ whose two children are the vertices labeled $s$ and $t$ and $\psi_u=\epsilon$. Then, $f$ maps ${{\mathcal T}}''$ to a vector $v_{{{\mathcal T}}''}$ that is obtained from $v_{{{\mathcal T}}'}$ by replacing each of the two vector components $$[\psi_s](\epsilon)\text{ and } [\psi_t](\epsilon)\text{ with } [\epsilon](\epsilon),$$ and replacing the vector component $$[\epsilon](y_{u}^1,y_{u}^2,\ldots,y_{u}^{r_u},\epsilon) \text{ with } [b](y_{u}^1,y_{u}^2\ldots,y_{u}^{r_u},\epsilon).$$

For both cases, it is easily checked that $v_{{{\mathcal T}}''}$ is an $X$-vector that satisfies the suffix-property relative to $v_{{\mathcal T}}$.

We next show that $v_{{{\mathcal T}}''}$ satisfies the cherry-property relative to $v_{{\mathcal T}}$. By Lemma \[lem:cherries\], we have $c_{{{\mathcal T}}'}-c_{{{\mathcal T}}''}\in\{0,1\}$. If $c_{{{\mathcal T}}'}-1=c_{{{\mathcal T}}''}$ then, by construction, each cherry in ${{\mathcal T}}''$ is a cherry in ${{\mathcal T}}'$. Hence, as $v_{{{\mathcal T}}'}$ satisfies the cherry-property relative to $v_{{\mathcal T}}$, we have that $v_{{{\mathcal T}}''}$ satisfies the cherry-property relative to $v_{{\mathcal T}}$. Otherwise, if $c_{{{\mathcal T}}'}=c_{{{\mathcal T}}''}$, then the cherry $\{a,b\}$ in ${{\mathcal T}}'$ is replaced with a new cherry that contains $b$, while all other cherries in ${{\mathcal T}}'$ are also cherries in ${{\mathcal T}}''$ . First, suppose that ${{\mathcal T}}''$ is obtained from ${{\mathcal T}}'$ according to mapping (M1). Observe that $r_s\geq 1$. If $r_s\geq 2$, then $\{b,y_s^2\}$ is the new cherry and, thus, $v_{{{\mathcal T}}''}$ satisfies the cherry-property relative to $v_{{\mathcal T}}$. On the other hand, if $r_s=1$, let $[\psi_t](y_t^1,y_t^2,\ldots,y_t^{r_t},\epsilon)$ be the vector component in $v_{{{\mathcal T}}'}$ such that the vertices labeled $s$ and $t$ in ${{\mathcal T}}_{{\mathcal I}}$ have the same parent. Note that $t$ exists because, otherwise, $s$ is the root of ${{\mathcal T}}_{{\mathcal I}}$ and so the existence of a cherry in ${{\mathcal T}}''$ that is not a cherry in ${{\mathcal T}}'$ implies that $r_s\geq 2$; a contradiction. If $r_t\geq 1$, then $\{\psi_t,y_t^1\}$ is a cherry in ${{\mathcal T}}'$ and ${{\mathcal T}}''$. Thus, the sibling of $b$ in ${{\mathcal T}}''$ is not a leaf, thereby contradicting that $b$ is a leaf of a cherry in ${{\mathcal T}}''$. Hence, $[\psi_t](y_t^1,y_t^2,\ldots,y_t^{r_t},\epsilon)=[\psi_t](\epsilon)$. Now, as $[b](\epsilon)$ and $[\psi_t](\epsilon)$ are two vector components of $v_{{{\mathcal T}}''}$, it again follows that $v_{{{\mathcal T}}''}$ satisfies the cherry-property relative to $v_{{\mathcal T}}$. Second, suppose that ${{\mathcal T}}''$ is obtained from ${{\mathcal T}}'$ according to mapping (M2). Noting that $b$ is an element of the vector component $[\psi_u](y_u^1,y_u^2,\ldots,y_t^{r_u},\epsilon)$ with $\psi_u=b$ in $v_{{{\mathcal T}}''}$, the result can be established by using an argument that is similar to the previous case.

It remains to show that the mapping is one-to-one. Let ${{\mathcal T}}'$ and ${{\mathcal T}}''$ be two distinct elements in ${{\mathcal C}}({{\mathcal T}})\setminus\{\emptyset\}$. Since each element in ${{\mathcal C}}({{\mathcal T}})\setminus\{{{\mathcal T}}, \emptyset\}$ can be obtained from ${{\mathcal T}}$ by repeatedly deleting a leaf of a cherry and suppressing the resulting degree-2 vertex, there exists an element $\ell$ in $X$ that is a leaf in ${{\mathcal T}}'$ and not a leaf in ${{\mathcal T}}''$. Let $X'$ and $X''$ be the leaf set of ${{\mathcal T}}'$ and ${{\mathcal T}}''$, respectively. Noting that $v_{{\mathcal T}}$ is an $X$-vector that contains each element in $X$ exactly once, it follows from construction of the mapping that $v_{{{\mathcal T}}'}$ is an $X'$-vector that contains each element in $X'$ exactly once and that $v_{{{\mathcal T}}''}$ is an $X''$-vector that contains each element in $X''$ exactly once. Hence $v_{{{\mathcal T}}'}\ne v_{{{\mathcal T}}''}$. Moreover, since no element in ${{\mathcal C}}({{\mathcal T}})\setminus\{\emptyset\}$ is mapped to $v_\emptyset$, the mapping is one-to-one. This completes the proof of the lemma.

\[lem:|C(T)|\] Let ${{\mathcal T}}$ be a rooted binary phylogenetic $X$-tree. Then $$|{{\mathcal C}}({{\mathcal T}})|\leq (|X|+1)^{4c_{{\mathcal T}}-2}.$$

Let $$\begin{aligned}
v_{{{\mathcal T}}}=&(&[\xi_1](x_{1}^1,x_{1}^2,\ldots,x_{1}^{q_1},\epsilon),\nonumber\\
&&[\xi_2](x_{2}^1,x_{2}^2,\ldots,x_{2}^{q_2},\epsilon),\nonumber\\
&&\vdots \nonumber\\
&&[\xi_n](x_n^1,x_n^2,\ldots,x_n^{q_n},\epsilon)\hspace{0.3cm})\nonumber\end{aligned}$$ be the vector representation of ${{\mathcal T}}$ relative to an index tree of ${{\mathcal T}}$, where $n=2c_{{\mathcal T}}-1$. We first derive an upper bound on the number of $X$-vectors that satisfy the suffix-property relative to $v_{{\mathcal T}}$. For each $i\in\{1,2,\ldots,n\}$, consider the vector component $[\xi_i](x_{i}^1,x_{i}^2,\ldots,x_{i}^{q_i},\epsilon)$. Then each $X$-vector that satisfies the suffix-property relative to ${{\mathcal T}}$ has an $i$th vector component, say $[\psi_i](y_{i}^1,y_{i}^2,\ldots,y_{i}^{r_i},\epsilon)$, such that $\psi_i\in X\cup\{\epsilon\}$ and $(y_{i}^1,y_{i}^2,\ldots,y_{i}^{r_i},\epsilon)$ is a suffix of $(x_{i}^1,x_{i}^2,\ldots,x_{i}^{q_i},\epsilon)$. Since there are at most $|X|+1$ such suffixes, it follows that there are at most $(|X|+1)^2$ variations of $[\psi_i](y_{i}^1,y_{i}^2,\ldots,y_{i}^{r_i},\epsilon)$. Hence, there are at most $$((|X| + 1)^2)^n = (|X| + 1)^{4c_{{\mathcal T}}-2}.$$ $X$-vectors that satisfy the suffix-property relative to $v_{{\mathcal T}}$. By Lemma \[l:map\], each tree in ${{\mathcal C}}({{\mathcal T}})$ can be mapped to one such vector and, as the map is one-to-one, it follows that ${{\mathcal C}}({{\mathcal T}})$ contains at most $(|X| + 1)^{4c_{{\mathcal T}}-2}$ trees.

For a rooted binary phylogenetic $X$-tree ${{\mathcal T}}$, the next lemma constructs an automaton that recognizes whether or not a word that contains each element in $X$ precisely once is a cherry-picking sequence for ${{\mathcal T}}$.

\[lem:automaton\] Let ${{\mathcal T}}$ be a rooted binary phylogenetic $X$-tree. There is a deterministic finite automaton ${{\mathcal A}}_{{\mathcal T}}$ with $O(|X|^{4c_{{\mathcal T}}-2})$ states that recognizes the language $${{\mathcal L}}_{X}({{\mathcal T}}) = \{x_1x_2\ldots x_{|X|} \mid (x_1,\,x_2,\,\ldots,\,x_{|X|}) \text{ is a cherry-picking sequence for } {{\mathcal T}}\}.$$ Moreover, the automaton ${{\mathcal A}}_{{\mathcal T}}$ can be constructed in time $f(|X|, c_{{\mathcal T}}) \in |X|^{O(c_{{\mathcal T}})}$.

Throughout this proof, we denote the tree without a vertex by $\emptyset$. Let $M$ and $M'$ be two sets. Setting $M = \{{{\mathcal T}}\}$ and $M' = \emptyset$, we construct ${{\mathcal A}}_{{\mathcal T}}$ as follows.

(1) Create the states $q_{{\mathcal T}}$, $q_\emptyset$, and $q_e$. For each $a \in X$, set $\delta(q_e, a) = \delta(q_\emptyset, a) = q_e$.

(2) For each ${{\mathcal T}}\in M$ and each $a \in X$ do the following.

    (a) If $a$ is a leaf of a cherry in ${{\mathcal T}}$ or $a$ is the only vertex of ${{\mathcal T}}$, then

        (i) create the state $q_{{{\mathcal T}}[-a]}$ if ${{\mathcal T}}[-a]$ is not isomorphic to a tree in $M'$,

        (ii) set $M' = M' \cup {{\mathcal T}}[-a]$, and

        (iii) set $\delta(q_{{{\mathcal T}}}, a) = q_{{{\mathcal T}}[-a]}$.

    (b) Otherwise, set $\delta(q_{{{\mathcal T}}}, a) = q_e$.

(3) Set $M = M'$ and, subsequently, set $M' = \emptyset$. If $M \neq \{\emptyset\}$, continue with $(2)$.

We set the initial state of ${{\mathcal A}}_{{\mathcal T}}$ to be $q_{{\mathcal T}}$ and the final state to be $q_\emptyset$. To illustrate, the construction of ${{\mathcal A}}_{{\mathcal T}}$ is shown in Figure \[fig:automaton\] for a phylogenetic tree on four leaves.

![Construction of an automaton that recognizes the language ${{\mathcal L}}_X({{\mathcal T}}_1)$ as described in the statement of Lemma \[lem:automaton\] and with ${{\mathcal T}}_1$ shown in the top left of this figure. Each vertex (resp. edge) represents a state (resp. transition). The vertex $q_{{{\mathcal T}}_1}$ indicates the initial state whereas the final state is $q_\emptyset$ as indicated by a double circle. To increase readability, most transitions to $q_e$ are omitted. In row $i$, the figure shows $M$, $M'$, and the automaton after the $i$th execution of the for-loop as described in Step (2) in the proof of Lemma \[lem:automaton\].[]{data-label="fig:automaton"}](automatonConstruction){width=".78\textwidth"}

By construction, we have ${{\mathcal A}}_{{\mathcal T}}=({{\mathcal C}}({{\mathcal T}}),X,\delta,q_{{\mathcal T}},\{q_\emptyset\})$. As each cherry-picked tree in ${{\mathcal C}}({{\mathcal T}})$ is mapped to a unique state, it follows from Lemma \[lem:|C(T)|\] that the number of states of ${{\mathcal A}}_{{\mathcal T}}$ is $O(|X|^{4c_{{\mathcal T}}-2})$. Moreover, for each $a\in X$ and each pair of two distinct states ${{\mathcal T}}',{{\mathcal T}}'' \in {{\mathcal C}}({{\mathcal T}})$, there is a transition $\delta(q_{{{\mathcal T}}'}, a) = q_{{{\mathcal T}}''}$ if and only if ${{\mathcal T}}'[-a] = {{\mathcal T}}''$ and $a$ is either a leaf of a cherry in ${{\mathcal T}}'$ or ${{\mathcal T}}'$ consists of the single vertex $a$. The state $q_e$ collects all inputs that do not correspond to the continuation of a cherry-picking sequence. More precisely, there is a transition $\delta(q_{{{\mathcal T}}'}, a) = q_{e}$ if and only if $a$ is not a leaf of a cherry in ${{\mathcal T}}'$ and ${{\mathcal T}}'$ does not consist of the single vertex $a$. It now follows that there is a one-to-one correspondence between the directed paths from $q_{{\mathcal T}}$ to $q_\emptyset$ in ${{\mathcal A}}_{{\mathcal T}}$ and the cherry-picking sequences of ${{\mathcal T}}$ and, hence, ${{\mathcal A}}_{{\mathcal T}}$ recognizes ${{\mathcal L}}_{X}({{\mathcal T}})$.

The time taken to construct ${{\mathcal A}}_{{\mathcal T}}$ is dominated by the number of iterations of the for-loop in Step $(2)$. Since $|M| < |{{\mathcal C}}({{\mathcal T}})|$ and $|{{\mathcal C}}({{\mathcal T}})| \in O(|X|^{4c_{{\mathcal T}}- 2})$, the number of iterations in Step (2) is $O(|{{\mathcal C}}({{\mathcal T}})|\cdot|X|) \subseteq O(|X|^{4c_{{\mathcal T}}- 1})$. Moreover, since Step (2) is executed $|X|$ times, each operation of the for-loop is executed $O(|X|^{4c_{{\mathcal T}}})$ times in total. While the complexity of these operations depend on the implementation and data structure, they can clearly be implemented such that ${{\mathcal A}}_{{\mathcal T}}$ can be constructed in time $|X|^{O(c_{{\mathcal T}})}$. This establishes the lemma.

Generalizing the language that is described in the statement of Lemma \[lem:automaton\], the next straightforward observation describes a language for the decision problem [CPS-Existence]{}.

\[obs:CPS\_language\_problem\] Let ${{\mathcal P}}=\{{{\mathcal T}}_1,{{\mathcal T}}_2,\ldots,{{\mathcal T}}_m\}$ be a collection of rooted binary phylogenetic $X$-trees. Then, solving [CPS-Existence]{} for ${{\mathcal P}}$ is equivalent to deciding if $$\bigcap_{1\leq i\leq m} {{\mathcal L}}_X({{\mathcal T}}_i) \neq \emptyset.$$

We are now in a position to establish Theorem \[t:cherry\].

[*Proof of Theorem \[t:cherry\].*]{} By Observation \[obs:CPS\_language\_problem\], it follows that there is a cherry-picking sequence for ${{\mathcal P}}$ if and only if $
\bigcap_{{{\mathcal T}}_i \in {{\mathcal P}}} {{\mathcal L}}_X({{\mathcal T}}_i) \neq \emptyset, 
$ where $${{\mathcal L}}_{X}({{\mathcal T}}) = \{x_1x_2\ldots x_{|X|} \mid (x_1,\,x_2,\,\ldots,\,x_{|X|}) \text{ is a cherry-picking sequence for } {{\mathcal T}}\}.$$

For each ${{\mathcal T}}_i \in {{\mathcal P}}$ with $1 \leq i \leq m$, we follow the notation and construction that is described in the proof of Lemma \[lem:automaton\] to obtain an automaton ${{\mathcal A}}_{{{\mathcal T}}_i}$ with $O(|X|^{4c_{{{\mathcal T}}_i}-2})$ states that recognizes the language ${{\mathcal L}}_X({{\mathcal T}}_i)$. To solve the question whether or not the intersection of these $m$ languages is empty, we use the well-known construction of a product automaton [@kozen97] as follows.

For each ${{\mathcal T}}_i \in {{\mathcal P}}$, let $Q_{{{\mathcal T}}_i}$ be set of states, and let $\delta_{{{\mathcal T}}_i}$ be the transition relation of ${{\mathcal A}}_{{{\mathcal T}}_i}$. We construct a new automaton ${{\mathcal A}}_{{{\mathcal P}}}$, where the set of states $Q_{{\mathcal P}}$ is the cartesian product $Q_{{{\mathcal T}}_1} \times Q_{{{\mathcal T}}_2}\times \ldots \times Q_{{{\mathcal T}}_{m}}$. Furthermore, the alphabet of ${{\mathcal A}}_{{{\mathcal P}}}$ is $X$ and the transition relation $\delta_{{\mathcal P}}\colon Q_{{\mathcal P}}\times X \rightarrow Q_{{\mathcal P}}$ is defined as $$\delta_{{\mathcal P}}((q_1,\ldots,q_m), a) = (\delta_{{{\mathcal T}}_1}(q_1, a),\, \ldots,\, \delta_{{{\mathcal T}}_m}(q_m, a)).$$ Lastly, the initial (resp. final) state of ${{\mathcal A}}_{{\mathcal P}}$ is $(q_1,\ldots,q_m)$ where, for all $i\in\{1,2,\ldots,m\}$, $q_i$ is the initial (resp. final) state of ${{\mathcal A}}_{{{\mathcal T}}_i}$. Intuitively, ${{\mathcal A}}_{{\mathcal P}}$ simulates the parallel execution of the automata ${{\mathcal A}}_{{{\mathcal T}}_1},{{\mathcal A}}_{{{\mathcal T}}_2},\ldots,{{\mathcal A}}_{{{\mathcal T}}_m}$. By construction, an input sequence is accepted by ${{\mathcal A}}_{{\mathcal P}}$ if and only if it is accepted by each automaton ${{\mathcal A}}_{{{\mathcal T}}_i}$. It now follows that there is a cherry-picking sequence for ${{\mathcal P}}$ if and only if the final state of ${{\mathcal A}}_{{\mathcal P}}$ can be reached from the initial state of ${{\mathcal A}}_{{\mathcal P}}$ and, hence, ${{\mathcal L}}({{\mathcal A}}_{{\mathcal P}}) \neq \emptyset$.

It remains to show that the computational complexity is as claimed in the statement of the theorem. Viewing ${{\mathcal A}}_{{\mathcal P}}$ as a directed graph, each directed path from the initial to the final state of ${{\mathcal A}}_{{\mathcal P}}$ has length $|X|$. We can therefore decide whether the final state from ${{\mathcal A}}_{{\mathcal P}}$ is reachable by using breadth-first search [@cormen09] in time $O(|Q_{{\mathcal P}}| + |X| \cdot |Q_{{\mathcal P}}|)$, where $|X| \cdot |Q_{{\mathcal P}}|$ is the number of transitions in ${{\mathcal A}}_{{\mathcal P}}$. By construction and Lemma \[lem:automaton\], it follows that ${{\mathcal A}}_{{\mathcal P}}$ has $$O\left(\prod_{i=1}^m |X|^{4c_{{{\mathcal T}}_i}-2}\right) \subseteq O(|X|^{m(4c-2)})$$ states, i.e. $|Q_{{\mathcal P}}| \in O(|X|^{m(4c-2)})$. Hence, we can decide in time $O(|X|^{m(4c-2)+1})$ whether ${{\mathcal L}}({{\mathcal A}}_{{\mathcal P}}) \neq \emptyset$. By Lemma \[lem:automaton\], it takes time $f_i(|X|, c_{{{\mathcal T}}_i}) \in |X|^{O(c_{{{\mathcal T}}_i})}$ to construct each automaton ${{\mathcal A}}_{{{\mathcal T}}_i}$ and, thus, it follows that deciding if there is a cherry-picking sequence for ${{\mathcal P}}$ can be done in time $$O\left (|X|^{m(4c-2)+1} + \sum_{i=1}^m f_i(|X|, c_{{{\mathcal T}}_i})\right ),$$ which is polynomial in $|X|$ if $c$ and $m$ are constant.\

Concluding remarks {#sec:con}
==================

In this paper, we have shown that [CPS-Existence]{}, a problem of relevance to the construction of phylogenetic networks from a set of phylogenetic trees, is NP-complete for all sets ${{\mathcal P}}$ of rooted binary phylogenetic trees with $|{{\mathcal P}}|\geq 8$. This result partially answers a question posed by Humphries et al. [@humphries13]. They asked if [CPS-Existence]{} is computationally hard for $|{{\mathcal P}}|=2$. To establish our result, we first showed that [$4$-Disjoint-Intermezzo]{}, which is a variant of the [Intermezzo]{} problem that is new to this paper, is NP-complete. Subsequently, we established a reduction from an instance $I$ of [$4$-Disjoint-Intermezzo]{} to an instance $I'$ of [CPS-Existence]{} with $|{{\mathcal P}}|=8$. Since each of the four collections of pairs and triples in $I$ reduces to two trees in $I'$, a possible approach to obtain a stronger hardness result for [CPS-Existence]{} with $|{{\mathcal P}}|<8$ is to show that [$N$-Disjoint-Intermezzo]{} is NP-complete for $N<4$. However, it seems likely that such a result can only be achieved by following a strategy that is different from the one that we used in this paper. In particular, there is no obvious reduction from [2P2N-3-SAT]{} to [$3$-Disjoint-Intermezzo]{}. Moreover, [$1$-Disjoint-Intermezzo]{} is solvable in polynomial time since all pairs and triples are pairwise disjoint and, so, it cannot be used for a reduction even if [CPS-Existence]{} turns out to be NP-complete for $|{{\mathcal P}}|=2$.

In the second part of the paper, we have translated [CPS-Existence]{} into an equivalent problem on languages and used automata theory to show that [CPS-Existence]{} can be solved in polynomial time if the number of trees in ${{\mathcal P}}$ and the number of cherries in each such tree are bounded by a constant. There are currently only a small number of other problems in phylogenetics that have been solved with the help of automata theory (e.g. [@hall10; @westesson12]) and it is to be hoped that the results presented in this paper will stimulate further research to explore connections between combinatorial problems in phylogenetics and automata theory.

[**Acknowledgements**]{}

We thank Britta Dorn for insightful comments on a draft version of this paper. The second author was supported by the New Zealand Marsden Fund.

[**References**]{}

[00]{} B. Albrecht, C. Scornavacca, A. Cenci, and D. H. Huson (2012). Fast computation of minimum hybridization networks. [*Bioinformatics*]{}, 28, 191–197.

M. Baroni, S. Gr[ü]{}newald, V. Moulton, and C. Semple, (2005), Bounding the number of hybridization events for a consistent evolutionary history, [*Journal of Mathematical Biology*]{}, 51, 171–182.

M. Baroni, C. Semple, and M. Steel (2006). Hybrids in real time. [*Systematic Biology*]{}, 55, 46–56.

M. Bordewich and C. Semple (2007). Computing the minimum number of hybridization events for a consistent evolutionary history. [*Discrete Applied Mathematics*]{}, 155, 914–928.

P. Berman, M. Karpinski, and A. D. Scott (2003). Approximation hardness of short symmetric instances of MAX-3SAT. [*Electronic Colloquium on Computational Complexity*]{}, Report No. 49.

G. Cardona, F. Rosselló, and G. Valiente (2009). Comparison of tree-child phylogenetic networks. [*IEEE/ACM Transactions on Computational Biology and Bioinformatics*]{}, 6, 552–569.

Z. Z. Chen and L. Wang (2013). An ultrafast tool for minimum reticulate networks. [*Journal of Computational Biology*]{}, 20, 38–41.

T. H. Cormen, C. E. Leierson, R. L. Rivest, and C. Stein (2009). Introduction to Algorithms. The MIT Press.

W. Guttmann and M. Maucher (2006). Variations on an ordering theme with constraints. In [*Fourth IFIP International Conference on Theoretical Computer Science*]{}, Springer, pp. 77–90.

D. Hall and D. Klein (2010). Finding cognate groups using phylogenies. In [*Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics*]{}, pp. 1030–1039.

J. E. Hopcroft and J. D. Ullman (1979). Introduction to Automata Theory, Languages, and Computation. Addison-Wesley.

P. J. Humphries, S. Linz, and C. Semple (2013). Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies. [*Bulletin of Mathematical Biology*]{}, 75, 1879–1890.

P. J. Humphries, S. Linz, and C. Semple (2013). On the complexity of computing the temporal hybridization number for two phylogenies. [*Discrete Applied Mathematics*]{}, 161, 871–880.

D. H. Huson, R. Rupp, C. Scornavacca (2010). Phylogenetic networks: concepts, algorithms and applications. Cambridge University Press.

D. C. Kozen (1997). Automata and Computability. Undergraduate Texts in Computer Science. Springer.

J. Mallet, N. Besansky, and M. W. Hahn (2016). How reticulated are species? [*BioEssays*]{}, 38, 140–149.

B. M. E. Moret, L. Nakhleh, T. Warnow, C. R. Linder, A. Tholse, A. Padolina, J. Sun, and R. Timme (2004). Phylogenetic networks: modeling, reconstructibility, and accuracy. [*IEEE/ACM Transactions on Computational Biology and Bioinformatics*]{}, 1, 13–23.

T. Piovesan and S. Kelk: A simple fixed parameter tractable algorithm for computing the hybridization number of two (not necessarily binary) trees, [*IEEE/ACM Transactions on Computational Biology and Bioinformatics*]{}, 10, 18–25.

C. Semple (2007). Hybridization networks, pages 277–314. In Gascuel, O. and Steel, M., eds., [*Reconstructing Evolution: New Mathematical and Computational Advances*]{}, Oxford University Press.

S. M. Soucy, J. Huang, and J. P. Gogarten (2015). Horizontal gene transfer: building the web of life. [*Nature Reviews Genetics*]{}, 16, 472–482.

O. Westesson, G. Lunter, B. Paten, and Ian Holmes (2012). Accurate reconstruction of insertion-deletion histories by statistical phylogenetics. [*PLoS One*]{}, 7(4): e34572.

Y. Wu and J. Wang (2010). Fast computation of the exact hybridization number of two phylogenetic trees. In [*International Symposium on Bioinformatics Research and Applications*]{}, Springer, pp. 203–214.
