{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreibm3nem5pf7jyed447wjxghtpj3i5d72wtcl7hhvyt6rumj3gnwdi",
    "uri": "at://did:plc:4rgrdigiftglskeax4wvmsev/app.bsky.feed.post/3mexfeeduhrx2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2602.12959v1",
  "publishedAt": "2026-02-16T01:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Niels Holtgrefe",
    "Jannik Schestag",
    "Norbert Zeh"
  ],
  "textContent": "**Authors:** Niels Holtgrefe, Jannik Schestag, Norbert Zeh\n\nIn 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"
}