Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915796920303616 |
|---|---|
| author | Holtgrefe, Niels Schestag, Jannik Zeh, Norbert |
| author_facet | Holtgrefe, Niels Schestag, Jannik Zeh, Norbert |
| contents | In the Maximize Phylogenetic Diversity problem, we are given a phylogenetic tree that represents the genetic proximity of species, and we are asked to select a subset of species of maximum phylogenetic diversity to be preserved through conservation efforts, subject to budgetary constraints that allow only k species to be saved. This neglects that it is futile to preserve a predatory species if we do not also preserve at least a subset of the prey it feeds on. Thus, in the Optimizing PD with Dependencies ($ε$-PDD) problem, we are additionally given a food web that represents the predator-prey relationships between species. The goal is to save a set of k species of maximum phylogenetic diversity such that for every saved species, at least one of its prey is also saved. This problem is NP-hard even when the phylogenetic tree is a star. The $α$-PDD problem alters PDD by requiring that at least some fraction $α$ of the prey of every saved species are also saved. In this paper, we study the parameterized complexity of $α$-PDD. We prove that the problem is W[1]-hard and in XP when parameterized by the solution size k, the diversity threshold D, or their complements. When parameterized by the vertex cover number of the food web, $α$-PDD is fixed-parameter tractable (FPT). A key measure of the computational difficulty of a problem that is FPT is the size of the smallest kernel that can be obtained. We prove that, when parameterized by the distance to clique, 1-PDD admits a linear kernel. Our main contribution is to prove that $α$-PDD does not admit a polynomial kernel when parameterized by the vertex cover number plus the diversity threshold D, even if the phylogenetic tree is a star. This implies the non-existence of a polynomial kernel for $α$-PDD also when parameterized by a range of structural parameters of the food web, such as its dist[...] |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_12959 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies Holtgrefe, Niels Schestag, Jannik Zeh, Norbert Computational Complexity Data Structures and Algorithms In the Maximize Phylogenetic Diversity problem, we are given a phylogenetic tree that represents the genetic proximity of species, and we are asked to select a subset of species of maximum phylogenetic diversity to be preserved through conservation efforts, subject to budgetary constraints that allow only k species to be saved. This neglects that it is futile to preserve a predatory species if we do not also preserve at least a subset of the prey it feeds on. Thus, in the Optimizing PD with Dependencies ($ε$-PDD) problem, we are additionally given a food web that represents the predator-prey relationships between species. The goal is to save a set of k species of maximum phylogenetic diversity such that for every saved species, at least one of its prey is also saved. This problem is NP-hard even when the phylogenetic tree is a star. The $α$-PDD problem alters PDD by requiring that at least some fraction $α$ of the prey of every saved species are also saved. In this paper, we study the parameterized complexity of $α$-PDD. We prove that the problem is W[1]-hard and in XP when parameterized by the solution size k, the diversity threshold D, or their complements. When parameterized by the vertex cover number of the food web, $α$-PDD is fixed-parameter tractable (FPT). A key measure of the computational difficulty of a problem that is FPT is the size of the smallest kernel that can be obtained. We prove that, when parameterized by the distance to clique, 1-PDD admits a linear kernel. Our main contribution is to prove that $α$-PDD does not admit a polynomial kernel when parameterized by the vertex cover number plus the diversity threshold D, even if the phylogenetic tree is a star. This implies the non-existence of a polynomial kernel for $α$-PDD also when parameterized by a range of structural parameters of the food web, such as its dist[...] |
| title | Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies |
| topic | Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2602.12959 |