New FPT Algorithms for Finding the Temporal Hybridization Number for Sets of Phylogenetic Trees

We study the problem of finding a temporal hybridization network containing at most k reticulations, for an input consisting of a set of phylogenetic trees. First, we introduce an FPT algorithm for the problem on an arbitrary set of m binary trees with n leaves each with a running time of O(5ᵏ· n· m) O ( 5 k · n · m ) . We also present the concept of temporal distance , which is a measure for how close a tree-child network is to being temporal. Then we introduce an algorithm for computing a tree-child network with temporal distance at most d and at most k reticulations in O((8k)ᵈ5^ k· k· n· m) O ( ( 8 k ) d 5 k · k · n · m ) time. Lastly, we introduce an O(6ᵏk!· k· n²) O ( 6 k k ! · k · n 2 ) time algorithm for computing a temporal hybridization network for a set of two nonbinary trees. We also provide an implementation of all algorithms and an experimental analysis on their performance.