Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies This paper was accepted for an oral presentation at the 17th Latin American Theoretical Informatics Symposium (LATIN 2026) in Florianópolis, Brazil, April 2026.

Niels Holtgrefe, Jannik Schestag, Norbert Zeh · 2026

Read Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies This paper was accepted for an oral presentation at the 17th Latin American Theoretical Informatics Symposium (LATIN 2026) in Florianópolis, Brazil, April 2026. by Niels Holtgrefe, Jannik Schestag, Norbert Zeh (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2602-12959.txt.

Description

Saving species for conservation should preserve evolutionary diversity, but saving a predator without its prey is futile. Niels Holtgrefe, Jannik Schestag, and Norbert Zeh study phylogenetic diversity with dependencies: choose k species of maximum diversity such that each saved species keeps at least one prey species saved. The problem is NP-hard even for star-shaped trees.

A variant requires a fraction alpha of each saved species' prey to be saved as well. The authors prove alpha-PDD is W[1]-hard and in XP under solution size, diversity threshold, or complements, but fixed-parameter tractable under food-web vertex cover number. Their main result is negative: no polynomial kernel exists under vertex cover plus diversity threshold, even for star trees, ruling out small kernels across many structural parameters. Kernelisation limits thus bite hard for dependency-aware conservation.

Catalog record

CREATORNiels Holtgrefe, Jannik Schestag, Norbert Zeh
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE50 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2602-12959

Browse the full library · About the Tower of Babel