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 