Cherry picking: a characterization of the temporal hybridization number for a set of phylogenies.
Recently, we have shown that calculating the minimum-temporal-hybridization number for a set [Formula: see text] of rooted binary phylogenetic trees is NP-hard and have characterized this minimum number when [Formula: see text] consists of exactly two trees. In this paper, we give the first characterization of the problem for [Formula: see text] being arbitrarily large. The characterization is in terms of cherries and the existence of a particular type of sequence. Furthermore, in an online appendix to the paper, we show that this new characterization can be used to show that computing the minimum-temporal hybridization number for two trees is fixed-parameter tractable.
Department of Mathematics and Physics, North Carolina Central University, Durham, NC, USA, pjhumphries@gmail.com.
Peter J
PJ
Humphries
Simone
S
Linz
Charles
C
Semple
D000465:Algorithms; D019295:Computational Biology; D006824:Hybridization, Genetic; D055641:Mathematical Concepts; D008957:Models, Genetic; D010802:Phylogeny