Maximizing Network Phylogenetic Diversity
<|reference_start|>Maximizing Network Phylogenetic Diversity: 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 \textsc{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 $\mathcal{O}(2^r \log (k)(n+r))$~time, with~$n$ the total number of species in the network and~$r$ its reticulation number. Furthermore, we show that \textsc{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.<|reference_end|>
@article{van iersel2024maximizing,
    title={Maximizing Network Phylogenetic Diversity},
    author={Leo van Iersel and Mark Jones and Jannik Schestag and Celine
  Scornavacca and Mathias Weller},
    journal={arXiv preprint arXiv:2405.01091},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.01091},
    primaryClass={cs.CC}
}