A universal tree-based network with the minimum number of reticulations.

Abstract

A tree-based network N on X is universal if every rooted binary phylogenetic X-tree is a base tree for N. Hayamizu and, independently, Zhang constructively showed that, for all positive integers n, there exists an universal tree-based network on n leaves. For all n, Hayamizu’s construction contains Θ(n!) reticulations, while Zhang’s construction contains Θ(n2) reticulations. A simple counting argument shows that a universal tree-based network has Ω(nlogn) reticulations. With this in mind, Hayamizu as well as Steel posed the problem of determining whether or not such networks exist with O(nlogn) reticulations. In this paper, we show that, for all n, there exists a universal tree-based network on n leaves with O(nlogn) reticulations.