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

Bordewich, Magnus; Semple, Charles

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.

Citation

Bordewich, M., & Semple, C. (2018). A universal tree-based network with the minimum number of reticulations. Discrete Applied Mathematics, 250, 357-362. https://doi.org/10.1016/j.dam.2018.05.010

• Journal Article Type: Article
• Acceptance Date: May 6, 2018
• Online Publication Date: May 30, 2018
• Publication Date: Dec 11, 2018
• Deposit Date: May 10, 2018
• Publicly Available Date: May 30, 2019
• Journal: Discrete Applied Mathematics
• Print ISSN: 0166-218X
• Electronic ISSN: 1872-6771
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 250
• Pages: 357-362
• DOI: https://doi.org/10.1016/j.dam.2018.05.010
• Public URL: https://durham-repository.worktribe.com/output/1327131