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 