FW Publications
Below you can find my publications and preprints on Food Webs, with links and toggleable abstracts.
To filter by a certain topic, click one of the buttons.
2026
[5]
conference paper
Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies
Proceedings of the 17th Latin American Theoretical Informatics Symposium (LATIN 2026), 2026.
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 (\( \varepsilon \)-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 \( \alpha \)-PDD problem alters \( \varepsilon \)-PDD by requiring that at least some fraction \( \alpha \) of the prey of every saved species are also saved. In this paper, we study the parameterized complexity of \( \alpha \)-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, \( \alpha \)-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 \( \alpha \)-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 \( \alpha \)-PDD also when parameterized by a range of structural parameters of the food web, such as its distance to cluster, treewidth, pathwidth, feedback vertex set, and others.
The \( \alpha \)-PDD problem alters \( \varepsilon \)-PDD by requiring that at least some fraction \( \alpha \) of the prey of every saved species are also saved. In this paper, we study the parameterized complexity of \( \alpha \)-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, \( \alpha \)-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 \( \alpha \)-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 \( \alpha \)-PDD also when parameterized by a range of structural parameters of the food web, such as its distance to cluster, treewidth, pathwidth, feedback vertex set, and others.
@misc{holtgrefe2026limits,
title = {{Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies}},
author = {Holtgrefe, Niels and Schestag, Jannik and Zeh, Norbert},
booktitle = {Proceedings of the 17th Latin American Theoretical Informatics Symposium (LATIN 2026)},
organization = {Springer},
year = {2026},
archivePrefix = {arXiv},
eprint = {2602.12959}
}
[4]
conference paper
Weighted Food Webs Make Computing Phylogenetic Diversity So Much Harder
Proceedings of the 51st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2026):187-202, 2026.
In a phylogenetic tree, phylogenetic trees represent certain species and their likely ancestors. In such a tree, present-day species are leaves and an edge from \(u\) to \(v\) indicates that \(u\) is an ancestor of \(v\). Weights on these edges indicate the phylogenetic distance. The phylogenetic diversity (PD) of a set of species \(A\) is the total weight of edges that are on any path between the root of the phylogenetic tree and a species in \(A\). Selecting a small set of species that maximizes phylogenetic diversity for a given phylogenetic tree is an essential task in preservation planning, where limited resources naturally prevent saving all species. An optimal solution can be found with a greedy algorithm. However, when a food web representing predator-prey relationships is given, finding a set of species that optimizes phylogenetic diversity subject to the condition that each saved species should be able to find food among the preserved species is NP-hard. We present a generalization of this problem where, inspired by biological considerations, the food web has weighted edges to represent the importance of predator-prey relationships. We show that this version is NP-hard even when both structures, the food web and the phylogenetic tree, are stars. To cope with this intractability, we proceed in two directions. Firstly, we study special cases where a species can only survive if a given fraction of its prey is preserved. Secondly, we analyze these problems through the lens of parameterized complexity. Our results include that finding a solution is fixed-parameter tractable with respect to the vertex cover number of the food web, assuming the phylogenetic tree is a star.
@inproceedings{schestag2026weighted,
title = {{Weighted Food Webs Make Computing Phylogenetic Diversity So Much Harder}},
author = {Schestag, Jannik},
booktitle = {Proceedings of the 51st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2026)},
pages = {187--202},
year = {2026},
organization = {Springer},
doi = {10.1007/978-3-032-17801-5_14}
}
[3]
preprint
The First Known Problem That Is FPT with Respect to Node Scanwidth but Not Treewidth
arXiv:2602.06903, 2026.
Structural parameters of graphs, such as treewidth, play a central role in the study of parameterized complexity. Motivated by the study of parameterized algorithms on phylogenetic networks, scanwidth was introduced recently as a new treewidth-like structural parameter for directed acyclic graphs that respects edge directions. While previous results showed that scanwidth often yields simpler and faster algorithms than treewidth, all previously studied problems were either fixed-parameter tractable with respect to both measures or hard for both. In this paper, we show that scanwidth is not merely a proxy for treewidth. Specifically, we prove that Weighted PDD is fixed-parameter tractable with respect to the scanwidth of the food web but W[\(\ell\)]-hard with respect to its treewidth for every \(\ell \ge 1\). To the best of our knowledge, this is the first natural problem exhibiting such a separation.
@article{schestag2026first,
title = {{The First Known Problem That Is FPT with Respect to Node Scanwidth but Not Treewidth}},
author = {Schestag, Jannik and Zeh, Norbert},
year = {2026},
archivePrefix = {arXiv},
journal = {arXiv preprint},
eprint = {2602.06903}
}
2025
[2]
conference paper
Parameterized Algorithms for Diversity of Networks with Ecological Dependencies
Proceedings of the 20th International Symposium on Parameterized and Exact Computation (IPEC 2025):11:1-11:21, 2025.
For a phylogenetic tree, the phylogenetic diversity of a set \(A\) of taxa is the total weight of edges on paths to \(A\). Finding small sets of maximal diversity is crucial for conservation planning, as it indicates where limited resources can be invested most efficiently. In recent years, efficient algorithms have been developed to find sets of taxa that maximize phylogenetic diversity either in a phylogenetic network or in a phylogenetic tree subject to ecological constraints, such as a food web. However, these aspects have mostly been studied independently. Since both factors are biologically important, it seems natural to consider them together. In this paper, we introduce decision problems where, given a phylogenetic network, a food web, and integers \(k\) and \(D\), the task is to find a set of \(k\) taxa with phylogenetic diversity of at least \(D\) under the maximize-all-paths measure while also satisfying viability conditions within the food web. We investigate the parameterized complexity of these problems and present several fixed-parameter tractable algorithms. Specifically, we provide a complete complexity dichotomy characterizing which combinations of parameters lead to W[1]-hardness and which admit fixed-parameter tractable algorithms. Our primary methodological contribution is a novel algorithmic framework for solving phylogenetic diversity problems in networks where dependencies impose an order, using a color-coding approach.
@inproceedings{jones2025parameterized,
title = {{Parameterized Algorithms for Diversity of Networks with Ecological Dependencies}},
author = {Jones, Mark and Schestag, Jannik},
booktitle = {Proceedings of the 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)},
pages = {11:1--11:21},
year = {2025},
organization = {Schloss-Dagstuhl-Leibniz Zentrum f{"u}r Informatik},
doi = {10.4230/LIPIcs.IPEC.2025.11}
}
2024
[1]
conference paper
Maximizing Phylogenetic Diversity under Ecological Constraints: A Parameterized Complexity Study
Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024):28:1-28:18, 2024.
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 describing 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 resulting subtree has total edge weight at least \(D\). We provide the first systematic analysis of PDD and its special case with star trees from a parameterized complexity perspective. For solution-size related parameters, we show that PDD is fixed-parameter tractable 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 and provide several fixed-parameter tractability results. Finally, we show that the star-tree variant admits a fixed-parameter algorithm for the treewidth of the food web, disproving a conjecture of Faller et al. that the problem remains NP-hard even when the food web is a tree.
@inproceedings{komusiewicz2024maximizing,
title = {{Maximizing Phylogenetic Diversity under Ecological Constraints: A Parameterized Complexity Study}},
author = {Komusiewicz, Christian and Schestag, Jannik},
booktitle = {Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)},
year = {2024},
pages = {28:1--28:18},
organization = {Schloss-Dagstuhl-Leibniz Zentrum f{"u}r Informatik},
doi = {10.4230/LIPIcs.FSTTCS.2024.28}
}