Abstract: We consider the NP-hard Tree Containment problem that has important applications in phylogenetics. The problem asks if a given single-rooted leaf-labeled network (“phylogenetic network”) N contains a subdivision of a given leaf-labeled tree (“phylogenetic tree”) T . We develop a fast algorithm for the case that N is a phylogenetic tree in which multiple leaves might share a label. Generalizing a previously known decomposition scheme lets us leverage this algorithm, yielding linear-time algorithms for so-called “reticulation visible” networks and “nearly stable” networks. While these are special classes of networks, they rank among
the most general of the previously considered cases. We also present a dynamic programming algorithm that solves the general problem in O(3^t·|N|·|T|) time, where the parameter t is the maximum number of tree components with unstable roots in any block of the input network. Notably, t is stronger (that is, smaller on all networks) than the previously considered parameter “number of reticulations” and even the popular parameter “level” of the input network.

return to ‘Accepted Papers’