Reticulation-visible networks

Abstract

Let $X$ be a finite set, $\mathcal{N}$ be a reticulation-visible network on $X$, and $\mathcal{T}$ be a rooted binary phylogenetic tree. We show that there is a polynomial-time algorithm for deciding whether or not $\mathcal{N}$ displays $\mathcal{T}$. Furthermore, for all $|X|\ge 1$, we show that $\mathcal{N}$ has at most $8|X|-7$ vertices in total and at most $3|X|-3$ reticulation vertices, and that these upper bounds are sharp.