  Here we show that deciding whether two rooted binary phylogenetic trees on
the same set of taxa permit a cherry-picking sequence, a special type of
elimination order on the taxa, is NP-complete. This improves on an earlier
result which proved hardness for eight or more trees. Via a known equivalence
between cherry-picking sequences and temporal phylogenetic networks, our result
proves that it is NP-complete to determine the existence of a temporal
phylogenetic network that contains topological embeddings of both trees. The
hardness result also greatly strengthens previous inapproximability results for
the minimum temporal-hybridization number problem. This is the optimization
version of the problem where we wish to construct a temporal phylogenetic
network that topologically embeds two given rooted binary phylogenetic trees
and that has a minimum number of indegree-2 nodes, which represent events such
as hybridization and horizontal gene transfer. We end on a positive note,
pointing out that fixed parameter tractability results in this area are likely
to ensure the continued relevance of the temporal phylogenetic network model.
