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).
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.
@inproceedings{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}
}
[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.
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 [Steel, Systematic Biology, 2005; Pardi and Goldman, PLoS Genetics, 2005]. 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 [Spillner et al., IEEE/ACM, 2008].
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.
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 [Steel, Systematic Biology, 2005; Pardi and Goldman, PLoS Genetics, 2005]. 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 [Spillner et al., IEEE/ACM, 2008].
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.
Structural parameters of graphs, such as treewidth, play a central role in the study of the parameterized complexity of graph problems. Motivated by the study of parametrized algorithms on phylogenetic networks, scanwidth was introduced recently as a new treewidth-like structural parameter for acyclic directed graphs (DAGs) that respects the edge directions in the DAG. The utility of this width measure has been demonstrated by results that show that a number of problems that are fixed-parameter-tractable (FPT) with respect to both treewidth and scanwidth allow algorithms with a better dependence on scanwidth than on treewidth. More importantly, these scanwidth-based algorithms are often much simpler than their treewidth-based counterparts: the name ``scanwidth'' reflects that traversing a tree extension (the scanwidth-equivalent of a tree decomposition) of a DAG amounts to ``scanning'' the DAG according to a well-chosen topological ordering. While these results show that scanwidth is useful especially for solving problems on phylogenetic networks, all problems studied through the lens of scanwidth so far are either FPT with respect to both scanwidth and treewidth, or W[\(\ell\)]-hard, for some \(\ell \ge 1\), with respect to both. In this paper, we show that scanwidth is not just a proxy for treewidth and provides information about the structure of the input graph not provided by treewidth, by proving a fairly stark complexity-theoretic separation between these two width measures. Specifically, we prove that Weighted-PDD is FPT with respect to the scanwidth of the food web but W[\(\ell\)]-hard with respect to its treewidth, for all \(\ell \ge 1\). To the best of our knowledge, no such separation between these two width measures has been shown for any natural problem before.
@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.
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. Here, we consider different definitions of viability, which all demand that a ``sufficient'' number of prey species survive to support surviving predators.
We investigate the parameterized complexity of these problems and present several fixed-parameter tractable (FPT) algorithms. Specifically, we provide a complete complexity dichotomy characterizing which combinations of parameters---out of the size constraint \(k\), the acceptable diversity loss \(\overline{D}\), the scanwidth of the food web \(sw\), the maximum in-degree \(\delta\) in the network, and the network height \(h\)---lead to W[1]-hardness and which admit FPT algorithms.
Our primary methodological contribution is a novel algorithmic framework for solving phylogenetic diversity problems in networks where dependencies (such as those from a food web) impose an order, using a color coding approach.
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. Here, we consider different definitions of viability, which all demand that a ``sufficient'' number of prey species survive to support surviving predators.
We investigate the parameterized complexity of these problems and present several fixed-parameter tractable (FPT) algorithms. Specifically, we provide a complete complexity dichotomy characterizing which combinations of parameters---out of the size constraint \(k\), the acceptable diversity loss \(\overline{D}\), the scanwidth of the food web \(sw\), the maximum in-degree \(\delta\) in the network, and the network height \(h\)---lead to W[1]-hardness and which admit FPT algorithms.
Our primary methodological contribution is a novel algorithmic framework for solving phylogenetic diversity problems in networks where dependencies (such as those from a food web) 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.
In the NP-hard Optimizing Phylogenetic Diversity with Dependencies (PDD) problem, the input consists of a phylogenetic tree \(\mathcal{T}\) 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 \(\mathcal{T}\) 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, PDD_s, 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 PDD_s 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 PDD_s is NP-hard even when the food-web is a tree.
We provide the first systematic analysis of PDD and its special case with star trees, PDD_s, 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 PDD_s 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 PDD_s is 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}
}