Linear-Time Tree Containment in Phylogenetic Networks

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