2024/05/02 by Leo van Iersel, van Iersel, Leo, Mark Jones +7 · 2 citations
Biochemistry, Genetics and Molecular Biology · #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Genomics and Phylogenetic Studies
paper · pdf · doi:10.48550/arxiv.2405.01091
openalex publication_date 2024/05/02 · openalex created_date 2024/05/05 · openalex updated_date 2026/07/28
Network Phylogenetic Diversity (Network-PD) is a measure for the diversity of a set of species based on a rooted phylogenetic network (with branch lengths and inheritance probabilities on the reticulation edges) describing the evolution of those species. We consider the Max-Network-PD problem: Given such a network, find k species with maximum Network-PD score. We show that this problem is fixed-parameter tractable (FPT) for binary networks, by describing an optimal algorithm running in O(2r log(k)(n + r)) time, with n the total number of species in the network and r its reticulation number. Furthermore, we show that Max-Network-PD is NP-hard for level-1 networks, proving that, unless P=NP, the FPT approach cannot be extended by using the level as parameter instead of the reticulation number.