Locating a tree in a phylogenetic network in quadratic time

Abstract. A fundamental problem in the study of phylogenetic net-works is to determine whether or not a given phylogenetic network con-tains a given phylogenetic tree. We develop a quadratic-time algorithm for this problem for binary nearly-stable phylogenetic networks. We also show that the number of reticulations in a reticulation visible or nearly stable phylogenetic network is bounded from above by a function linear in the number of taxa.