Who Should Have a Place on the Ark? Parameterized algorithms for the maximization of the Phylogenetic Diversity

Phylogenetic Diversity (PD) is a well-regarded measure of the overall biodiversity of a set of present-day species (taxa) that indicates its ecological signiőcance. In the Maximize Phylogenetic Diversity (Max-PD) roblem one is asked to őnd a small set of taxa in a phylogenetic tree for which this measure is maximized. Max-PD is particularly relevant in conservation planning, where limited resources necessitate prioritizing certain taxa to minimize biodiversity loss. Although Max-PD can be solved in polynomial time [Steel, Systematic Biology, 2005; Pardi and Goldman, PLoS Genetics, 2005], its generalizationsÐwhich aim to model biological processes and other aspects in conservation planning with greater accuracyÐoften exhibit NP-hardness, making them computationally challenging. This thesis explores a selection of these generalized problems within the framework of parameterized complexity. In Generalized Noah’s Ark Problem (GNAP), each taxon only survives at a certain survival probability, which can be increased by investing more money in the taxon. We show that GNAP is W[1]-hard with respect to the number of taxa but is XP with respect to the number of different costs and different survival probabilities. Additionally, we show that unit-cost-NAP, a special case of GNAP, is NP-hard. In Time Sensitive Maximization of Phylogenetic Diversity (Time-PD), different extinction times of taxa are considered after which they can no longer be saved. For Time-PD, we present color-coding algorithms that prove that Time-PD is őxed-parameter tractable (FPT) with respect to the threshold of diversity and the acceptable loss of diversity. In Optimizing PD with Dependencies (PDD), each saved taxon must be a source in the ecological system or a predator of another saved species. These dependencies are given in a food-web. We show that PDD is FPT when parameterized with the size of the solution plus the height of the phylogenetic tree. Further, we consider parameters characterizing the food-web and prove that PDD is FPT with respect to the treewidth if the phylogenetic tree is a star, disproving an open conjecture. Phylogenetic Diversity is traditionally deőned on phylogenetic trees, but phylogenetic networks have gained popularity as they enable the modeling of so-called reticulation events. Max-All-Paths-PD (MapPD) and Max-Net-PD are two problems in maximizing phylogenetic diversity on phylogenetic networks. MapPD is W[2]-hard with respect to the solution size but we show that MapPD is FPT with respect to the number of reticulations and the treewidth, two parameters that show how tree-like the phylogenetic network is. Max-Net-PD however remains NP-hard even on level-1-networks.