2026-07-26T10:49:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22217 2024-12-05T15:18:04Z ddc:004 open_access

Maximizing Phylogenetic Diversity Under Ecological Constraints: A Parameterized Complexity Study Komusiewicz, Christian Schestag, Jannik phylogenetic diversity food-webs structural parameterization color-coding dynamic programming In the NP-hard Optimizing Phylogenetic Diversity with Dependencies(PDD) problem, the input consists of a phylogenetic tree 𝒯 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 𝒯 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 with star trees, s-PDD, from a parameterized complexity perspective. For solution-size related parameters, we show that PDD is fixed-parameter tractable (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, unless P = NP, 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Christian Komusiewicz and Jannik Schestag 2024 Is Part Of LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2024.28 urn:nbn:de:0030-drops-222175 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.28 eng https://creativecommons.org/licenses/by/4.0/legalcode