SW Publications
Below you can find my publications and preprints on Scanwidth, with links and toggleable abstracts.
To filter by a certain topic, click one of the buttons.
2026
[5]
Average-Tree Phylogenetic Diversity Parameterized by Scanwidth and Invisibility
Leo van Iersel,
Mark Jones,
Jannik Schestag,
Celine Scornavacca, and
Mathias Weller
Proceedings of the 21st International Symposium on Parameterized and Exact Computation (IPEC 2026)
In terms of laymen
This paper investigates when the average amount of evolutionary history represented by selected species can be computed efficiently on complex evolutionary networks. It shows that subtle differences in how tree-like the network is can make the difference between an easy and a difficult problem, and gives fast algorithms for several important network structures.
In Laiensprache (German translation)
Diese Arbeit untersucht, unter welchen Bedingungen sich die durchschnittliche Menge an Evolutionsgeschichte, die durch ausgewählte Arten repräsentiert wird, auf komplexen evolutionären Netzwerken effizient berechnen lässt. Sie zeigt, dass bereits feine Unterschiede darin, wie baumähnlich ein Netzwerk ist, darüber entscheiden können, ob ein Problem leicht oder schwierig zu lösen ist, und entwickelt schnelle Algorithmen für mehrere wichtige Netzwerkstrukturen.
Abstract
We investigate parameterized algorithms for computing the average-tree phylogenetic diversity (APD) in rooted phylogenetic networks, studying the problem under different structural parameters that capture the deviation of a network from a tree. Our primary parameter is the scanwidth, a measure of the tree-likeness of a given directed acyclic graph. We show that a subset of taxa with maximum APD can be found in polynomial time in phylogenetic networks of scanwidth at most 2, but becomes NP-hard in networks of scanwidth 3. Further, we design an algorithm that computes the APD of a given set of taxa in \(\mathcal{O}(2^{\mathrm{sw}} n)\) time, where \(\mathrm{sw}\) denotes the scanwidth and \(n\) the number of taxa in the input network. Finally, we give a linear-time algorithm for computing the APD of a given set of taxa if the network induced by these taxa is reticulation-visible. We generalize this algorithm to still run in polynomial time if each biconnected component of the induced network has only constantly many invisible reticulations.
@inproceedings{vanIersel2026averagetree,
title = {{Average-Tree Phylogenetic Diversity Parameterized by Scanwidth and Invisibility}},
author = {van Iersel, Leo and Jones, Mark and Schestag, Jannik and Scornavacca, Celine and Weller, Mathias},
booktitle = {Proceedings of the 21th International Symposium on Parameterized and Exact Computation (IPEC 2026)},
year = {2026},
organization = {Schloss-Dagstuhl-Leibniz Zentrum f{\"u}r Informatik}
}
[4]
PaNDA: Efficient Optimization of Phylogenetic Diversity in Networks
Niels Holtgrefe,
Leo van Iersel,
Ruben Meuwese,
Yukihiro Murakami, and
Jannik Schestag
In terms of laymen
When only some species can be protected, conservationists would like to choose those that preserve as much evolutionary history as possible. PaNDA provides algorithms and an interactive software tool for solving and visualizing this problem on complex evolutionary networks, with experiments showing that realistically large networks can be handled efficiently.
In Laiensprache (German translation)
Wenn nur ein Teil der Arten geschützt werden kann, möchte man diejenigen auswählen, durch deren Schutz möglichst viel Evolutionsgeschichte erhalten bleibt. PaNDA stellt Algorithmen und ein interaktives Softwarewerkzeug bereit, mit denen dieses Problem auf komplexen evolutionären Netzwerken gelöst und visualisiert werden kann. Experimente zeigen, dass sich damit auch realistisch große Netzwerke effizient bearbeiten lassen.
Abstract
Phylogenetic diversity plays an important role in biodiversity, conservation, and evolutionary studies by measuring the diversity of a set of taxa based on their phylogenetic relationships. In phylogenetic trees, a subset of \(k\) taxa with maximum phylogenetic diversity can be found by a simple and efficient greedy algorithm. However, this algorithmic tractability is lost when considering phylogenetic networks, which incorporate reticulate evolutionary events such as hybridization and horizontal gene transfer. To address this challenge, we introduce PaNDA (Phylogenetic Network Diversity Algorithms), the first software package and interactive graphical user-interface for exploring, visualizing and maximizing diversity in phylogenetic networks. PaNDA includes a novel algorithm to find a subset of \(k\) taxa with maximum diversity, running in polynomial time for networks of bounded canwidth, a measure of tree-likeness of a network that grows slower than the well-known level measure. This algorithm considers the variant of phylogenetic diversity on networks in which the branch lengths of all paths from the root to the selected taxa contribute towards their diversity. We demonstrate the scalability of this algorithm on simulated networks, successfully analyzing level-15 networks with up to 200 taxa in seconds. We also provide a proof-of-concept analysis using a phylogenetic network on Xiphophorus species, illustrating how the tool can support diversity studies based on real genomic data. The software is easily installable and freely available at https://github.com/nholtgrefe/panda. Additionally, we extend the definition of phylogene- tic diversity to semi-directed phylogenetic networks, which are mixed graphs increasingly used in phylogenetic analysis to model uncertainty of the root location. We prove that finding a subset of \(k\) taxa with maximum diversity remains NP-hard on semi-directed networks, but do present a polynomial-time algorithm for networks with bounded level.
@article{holtgrefe2026panda,
title = {{PaNDA: Efficient Optimization of Phylogenetic Diversity in Networks}},
author = {Holtgrefe, Niels and van Iersel, Leo and Meuwese, Ruben and Murakami, Yukihiro and Schestag, Jannik},
year = {2026},
journal = {Journal of Computational Biology},
publisher={Springer},
doi = {10.1101/2025.11.14.688467}
}
[3]
Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth
Niels Holtgrefe and
Jannik Schestag
In terms of laymen
When conservation funds are limited and different species cost different amounts to protect, we would like to preserve as much evolutionary history as possible with the available budget. This paper develops efficient methods for doing this on sufficiently tree-like evolutionary networks and shows experimentally that the resulting algorithms can handle large networks quickly.
In Laiensprache (German translation)
Wenn die Mittel für den Artenschutz begrenzt sind und der Schutz verschiedener Arten unterschiedlich viel kostet, möchte man mit dem verfügbaren Budget möglichst viel Evolutionsgeschichte bewahren. Diese Arbeit entwickelt effiziente Methoden dafür auf evolutionären Netzwerken, die eine hinreichend baumähnliche Struktur besitzen, und zeigt experimentell, dass die Algorithmen auch große Netzwerke schnell bearbeiten können.
Abstract
Background: Identifying a subset of taxa that maximizes phylogenetic diversity is a cornerstone of quantitative conservation planning. Traditionally, phylogenetic diversity is defined over a phylogenetic tree in which leaves resemble present-day taxa and the branch lengths capture the estimated evolutionary distinctiveness. While maximizing phylogenetic diversity is computationally tractable on trees with unit costs, the problem becomes computationally intractable when transitioning to phylogenetic networks or to budgeted versions in which protecting taxa incurs non-homogeneous costs. This paper addresses these two challenges together, providing definitions and a comprehensive analysis of three distinct variants of budgeted phylogenetic diversity on networks.
Results: We conduct our study through the lens of a small structural parameter, node scanwidth (\(nsw\)), which measures the tree-likeness of a phylogenetic network. Given a tree-extension of width \(nsw\), we show that two of the considered variants can be optimized in \(\mathcal{O}^*(3^{nsw} \cdot B^2)\) time, where \(B\) is the budget. For the computationally harder third variant, we provide an algorithm to compute phylogenetic diversity scores in \(\mathcal{O}^*(4^{nsw})\) time. We further contribute the first exact algorithms to compute node scanwidth itself. On highly reticulated, simulated networks with several hundred taxa and heterogeneous costs, our implementation computes phylogenetic diversity scores and optimal node scanwidth in fractions of a second, and the budgeted optimization algorithms significantly outperform existing benchmarks previously limited to unit-cost scenarios.
Conclusions: Node scanwidth proves to be a small and computable parameter that makes budgeted phylogenetic diversity tractable on realistic networks, scaling comfortably to a thousand taxa. This narrows the gap between realistic models of reticulate evolution and the computational tools available for conservation planning.
Results: We conduct our study through the lens of a small structural parameter, node scanwidth (\(nsw\)), which measures the tree-likeness of a phylogenetic network. Given a tree-extension of width \(nsw\), we show that two of the considered variants can be optimized in \(\mathcal{O}^*(3^{nsw} \cdot B^2)\) time, where \(B\) is the budget. For the computationally harder third variant, we provide an algorithm to compute phylogenetic diversity scores in \(\mathcal{O}^*(4^{nsw})\) time. We further contribute the first exact algorithms to compute node scanwidth itself. On highly reticulated, simulated networks with several hundred taxa and heterogeneous costs, our implementation computes phylogenetic diversity scores and optimal node scanwidth in fractions of a second, and the budgeted optimization algorithms significantly outperform existing benchmarks previously limited to unit-cost scenarios.
Conclusions: Node scanwidth proves to be a small and computable parameter that makes budgeted phylogenetic diversity tractable on realistic networks, scaling comfortably to a thousand taxa. This narrows the gap between realistic models of reticulate evolution and the computational tools available for conservation planning.
@article{holtgrefe2026tractable,
title = {{Tractable Maximization of Budgeted Phylogenetic Diversity on Networks Utilizing Node Scanwidth}},
author = {Holtgrefe, Niels and Schestag, Jannik},
year = {2026},
journal = {arXiv preprint},
archivePrefix = {arXiv},
eprint = {2605.23319}
}
[2]
The First Known Problem That Is FPT with Respect to Node Scanwidth but Not Treewidth
Jannik Schestag and
Norbert Zeh
In terms of laymen
Computer scientists often measure how “tree-like” a network is because many difficult problems become easier on networks that resemble trees. This paper gives the first known problem for which a measure that takes the directions of connections into account makes efficient computation possible, while the classical undirected measure does not, showing that those directions can contain crucial algorithmic information.
In Laiensprache (German translation)
In der Informatik wird häufig gemessen, wie „baumähnlich“ ein Netzwerk ist, da sich viele schwierige Probleme auf besonders baumähnlichen Netzwerken leichter lösen lassen. Diese Arbeit beschreibt das erste bekannte Problem, bei dem ein Maß, das auch die Richtungen der Verbindungen berücksichtigt, eine effiziente Berechnung ermöglicht, während das klassische ungerichtete Maß dafür nicht ausreicht. Damit zeigt sie, dass die Richtungen der Verbindungen entscheidende algorithmische Informationen enthalten können.
Abstract
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
[1]
Parameterized Algorithms for Diversity of Networks with Ecological Dependencies
Mark Jones and
Jannik Schestag
Proceedings of the 20th International Symposium on Parameterized and Exact Computation (IPEC 2025)
In terms of laymen
Conservation decisions should take into account both how much evolutionary history species represent and whether the selected species can survive together in an ecosystem. This paper combines these two requirements by incorporating food-web dependencies into conservation planning on evolutionary networks and identifies several structural conditions under which the resulting problem can be solved efficiently.
In Laiensprache (German translation)
Entscheidungen im Artenschutz sollten sowohl berücksichtigen, wie viel Evolutionsgeschichte die ausgewählten Arten repräsentieren, als auch, ob diese Arten gemeinsam in einem Ökosystem überleben können. Diese Arbeit verbindet beide Anforderungen, indem sie Abhängigkeiten aus Nahrungsnetzen in die Schutzplanung auf evolutionären Netzwerken einbezieht. Sie identifiziert mehrere strukturelle Bedingungen, unter denen das entstehende Problem effizient gelöst werden kann.
Abstract
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}
}