On the existence of funneled orientations for classes of rooted phylogenetic networks
Recently, there has been a growing interest in the relationships between unrooted and rooted phylogenetic networks. In this context, a natural question to ask is if an unrooted phylogenetic network U can be oriented as a rooted phylogenetic network such that the latter satisfies certain structural properties. In a recent preprint, Bulteau et al. claim that it is computational hard to decide if U has a funneled (resp. funneled tree-child) orientation, for when the internal vertices of U have degree at most 5. Unfortunately, the proof of their funneled tree-child result appears to be incorrect. In this paper, we present a corrected proof and show that hardness remains for other popular classes of rooted phylogenetic networks such as funneled normal and funneled reticulation-visible. Additionally, our results hold regardless of whether U is rooted at an existing vertex or by subdividing an edge with the root.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Classes of Explicit Phylogenetic Networks and their Biological and Mathematical Significance
The evolutionary relationships among organisms have traditionally been represented using rooted phylogenetic trees. However, due to reticulate processes such as hybridization or lateral gene transfer, evolution cannot al…
Deciding the existence of a cherry-picking sequence is hard on two trees
Here we show that deciding whether two rooted binary phylogenetic trees on the same set of taxa permit a cherry-picking sequence, a special type of elimination order on the taxa, is NP-complete. This improves on an earli…
Locating a Tree in a Reticulation-Visible Network in Cubic Time
In this work, we answer an open problem in the study of phylogenetic networks. Phylogenetic trees are rooted binary trees in which all edges are directed away from the root, whereas phylogenetic networks are rooted acycl…
On the Complexity of Optimising Variants of Phylogenetic Diversity on Phylogenetic Networks
Phylogenetic Diversity (PD) is a prominent quantitative measure of the biodiversity of a collection of present-day species (taxa). This measure is based on the evolutionary distance among the species in the collection. L…
DiversityPlanar Rooted Phylogenetic Networks
A rooted phylogenetic network is a directed acyclic graph with a single root, whose sinks correspond to a set of species. As such networks are useful for representing the evolution of species that have undergone reticula…