---
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 