more positive note, we show that deciding if ${{\mathcal P}}$ has a cherry-picking sequence can be done in polynomial time if the number of trees and the number of cherries in each such tree are bounded by a constant. To this end, we explore connections between phylogenetic trees and automata theory and show how the problem at hand can be solved by using a deterministic finite automaton.

The remainder of the paper is organized as follows. The next section contains notation and terminology that is used throughout the paper. Section \[sec:intermezzo\] establishes NP-completeness of a variant of the [Intermezzo]{} problem which is then, in turn, used in Section \[sec:cps\] to show that it is NP-complete to decide if ${{\mathcal P}}$ has a cherry-picking sequence [for when $|{{\mathcal P}}|\geq 8$]{}. In Section \[sec:cherries\], we show that deciding if ${{\mathcal P}}$ has a cherry-picking sequence is polynomial-time solvable if the number of cherries in each tree and the size of ${{\mathcal P}}$ are bounded by a constant. We finish the paper with some concluding remarks in Section \[sec:con\].

Preliminaries {#sec:prelim}
=============

This section provides notation and terminology that is used in the subsequent sections. Throughout this paper, $X$ denotes a finite set.

