Maximizing Phylogenetic Diversity under Ecological Constraints: A Parameterized Complexity Study

In the NP-hard Optimizing PD with Dependencies (PDD) problem, the input consists of a phylogenetic tree T over a set of taxa X, a food-web that describes the prey-predator relationships in X, and integers k and D. The task is to find a set S of k species that is viable in the food-web such that the subtree of T obtained by retaining only the vertices of S has total edge weight at least D. Herein, viable means that for every predator taxon of S, the set S contains at least one prey taxon. We provide the first systematic analysis of PDD and its special case s-PDD from a parameterized complexity perspective. For solution-size related parameters, we show that PDD is FPT with respect to D and with respect to k plus the height of the phylogenetic tree. Moreover, we consider structural parameterizations of the food-web. For example, we show an FPT-algorithm for the parameter that measures the vertex deletion distance to graphs where every connected component is a complete graph. Finally, we show that s-PDD admits an FPT-algorithm for the treewidth of the food-web. This disproves a conjecture of Faller et al. [Annals of Combinatorics, 2011] who conjectured that s-PDD is NP-hard even when the food-web is a tree.