  Recently, the minimum number of reticulation events that is required to
simultaneously embed a collection 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 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 P has a cherry-picking sequence is NP-complete for when
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 P and the number of cherries in each such tree are
bounded by a constant.
