FPT Publications
Below you can find my publications and preprints on Parameterized Complexity, with links and toggleable abstracts.
To filter by a certain topic, click one of the buttons.
2026
[20]
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}
}
[19]
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}
}
[18]
Orienting Unrooted Binary Networks Faster: Focus on the Generator
Jannik Schestag and
Norbert Zeh
In terms of laymen
Evolutionary networks are sometimes reconstructed without directions on their connections, even though interpreting them as an evolutionary history requires deciding which way those connections point. This paper shows how to find suitable directions much faster when the complicated core of the network is small, covering the most relevant classes of evolutionary networks.
In Laiensprache (German translation)
Evolutionäre Netzwerke werden manchmal rekonstruiert, ohne dass die Verbindungen eine Richtung haben. Um ein solches Netzwerk als Evolutionsgeschichte interpretieren zu können, muss jedoch festgelegt werden, in welche Richtung die einzelnen Verbindungen verlaufen. Diese Arbeit zeigt, wie sich geeignete Richtungen deutlich schneller bestimmen lassen, wenn der komplizierte Kern des Netzwerks klein ist, und behandelt dabei die wichtigsten Klassen evolutionärer Netzwerke.
Abstract
The problem of orienting an unrooted network to obtain a specific class of rooted phylogenetic networks is known to be NP-hard in many cases. In this paper, we introduce two algorithmic frameworks that yield significantly improved fixed-parameter tractable (FPT) algorithms parameterized by the network level \(\ell\). Our first main contribution shows that for several prominent network classes, the core algorithmic difficulty lies in finding a directed spanning tree on the network's undirected generator. By enumerating these spanning trees in \(\mathcal{O}(5.3334^\ell + \ell)\) time and orienting all remaining edges in polynomial time, we solve the orientation problem in \(\mathcal{O}(5.3334^\ell \cdot n)\) time for tree-based networks and in \(\mathcal{O}(5.3334^\ell \cdot n^2)\) time for orchards, where \(n\) is the number of vertices of the graph. Extending this approach with further branching yields \(\mathcal{O}(10.6667^\ell \cdot n^2)\)-time algorithms for tree-child and normal networks. Our second technique bypasses spanning trees by directly guessing the placement of reticulations on the generator. This framework provides \(\mathcal{O}(12.2071^\ell \cdot n^2)\)-time algorithms for temporal, reticulation-visible, and tree-sibling networks. Finally, we demonstrate the versatility of the reticulation-guessing framework by showing that even computing an orientation with minimum scanwidth is single-exponential FPT with respect to the level. Together, these results significantly improve the best-known running times for phylogenetic network orientation.
@article{Schestag2026Orienting,
title = {{Orienting Unrooted Binary Networks Faster: Focus on the Generator}},
author = {Schestag, Jannik and Zeh, Norbert},
journal = {arXiv preprint},
year = {2026},
archivePrefix = {arXiv},
eprint = {2606.31597}
}
[17]
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}
}
[16]
A multivariate complexity analysis of the Generalized Noah's Ark Problem
Christian Komusiewicz and
Jannik Schestag
In terms of laymen
Suppose each endangered species can receive different conservation measures, each with its own cost and effect on the species' chance of survival. This paper studies how to choose among those measures under a limited budget so that as much evolutionary history as possible is expected to survive, and determines which aspects of the problem make this choice easier or harder to compute.
In Laiensprache (German translation)
Angenommen, für jede bedrohte Art stehen verschiedene Schutzmaßnahmen zur Verfügung, die jeweils unterschiedliche Kosten verursachen und ihre Überlebenswahrscheinlichkeit unterschiedlich stark erhöhen. Diese Arbeit untersucht, wie solche Maßnahmen bei begrenztem Budget ausgewählt werden sollten, damit voraussichtlich möglichst viel Evolutionsgeschichte erhalten bleibt. Außerdem wird bestimmt, welche Eigenschaften des Problems diese Entscheidung rechnerisch leichter oder schwieriger machen.
Abstract
In the Generalized Noah's Ark Problem, one is given a phylogenetic tree on a set of species \(X\) and a set of conservation projects for each species. Each project comes with a cost and raises the survival probability of the corresponding species. The aim is to select a conservation project for each species such that the total cost of the selected projects does not exceed some given threshold and the expected phylogenetic diversity is as large as possible. We study the complexity of Generalized Noah's Ark Problem and some of its special cases with respect to several parameters related to the input structure, such as the number of different costs, the number of different survival probabilities, or the number of species, \(|X|\).
@article{komusiewicz2026multivariate,
title = {{A multivariate complexity analysis of the Generalized Noah's Ark Problem}},
author = {Komusiewicz, Christian and Schestag, Jannik},
journal = {Discrete Applied Mathematics},
volume = {382},
pages = {137--154},
year = {2026},
publisher = {Elsevier},
doi = {10.1016/j.dam.2025.11.037}
}
[15]
Limits of Kernelization and Parametrization for Phylogenetic Diversity with Dependencies
Niels Holtgrefe,
Jannik Schestag, and
Norbert Zeh
Proceedings of the 17th Latin American Theoretical Informatics Symposium (LATIN 2026)
In terms of laymen
A conservation plan should not protect a predator while allowing too much of the prey it depends on to disappear. This paper studies how difficult it is to select an evolutionarily diverse set of species while respecting such food-web dependencies, identifying both situations where efficient solutions are possible and situations that remain fundamentally difficult.
In Laiensprache (German translation)
Ein Artenschutzplan sollte nicht ein Raubtier schützen, während gleichzeitig zu viele der Beutetiere verschwinden, von denen es abhängig ist. Diese Arbeit untersucht, wie schwierig es ist, eine evolutionär vielfältige Gruppe von Arten auszuwählen und dabei solche Abhängigkeiten im Nahrungsnetz zu berücksichtigen. Sie zeigt sowohl Situationen auf, in denen effiziente Lösungen möglich sind, als auch solche, die grundsätzlich schwierig bleiben.
Abstract
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}
}
[14]
Weighted Food Webs Make Computing Phylogenetic Diversity So Much Harder
Jannik Schestag
Proceedings of the 51st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2026)
In terms of laymen
Not every prey species is equally important to a predator, so a more realistic food web can assign different strengths to different feeding relationships. This paper shows that introducing these weights can make selecting an evolutionarily diverse and ecologically viable set of species dramatically harder, even when both the evolutionary tree and the food web are otherwise extremely simple.
In Laiensprache (German translation)
Nicht jede Beuteart ist für ein Raubtier gleich wichtig, weshalb ein realistischeres Nahrungsnetz verschiedenen Räuber-Beute-Beziehungen unterschiedliche Bedeutungen zuweisen kann. Diese Arbeit zeigt, dass solche Gewichtungen die Auswahl einer evolutionär vielfältigen und zugleich ökologisch überlebensfähigen Gruppe von Arten erheblich schwieriger machen können – selbst dann, wenn sowohl der Evolutionsbaum als auch das Nahrungsnetz ansonsten äußerst einfach aufgebaut sind.
Abstract
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}
}
[13]
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
[12]
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}
}
[11]
Average-Tree Phylogenetic Diversity of Networks
Leo van Iersel,
Mark Jones,
Jannik Schestag,
Celine Scornavacca, and
Mathias Weller
Proceedings of the 25th International Workshop on Algorithms in Bioinformatics (WABI 2025)
In terms of laymen
A phylogenetic network can represent many different possible evolutionary trees, with some histories being more likely than others. This paper measures the diversity of a set of species by averaging over these possible histories and shows that, although optimization is difficult in general, it can be practical when the network contains relatively few points where evolutionary histories merge.
In Laiensprache (German translation)
Ein phylogenetisches Netzwerk kann viele verschiedene mögliche Evolutionsbäume darstellen, wobei manche Evolutionsgeschichten wahrscheinlicher sind als andere. Diese Arbeit misst die Vielfalt einer Gruppe von Arten, indem über diese möglichen Geschichten gemittelt wird. Obwohl die Optimierung im Allgemeinen schwierig ist, kann sie effizient durchgeführt werden, wenn das Netzwerk nur relativ wenige Stellen besitzt, an denen unterschiedliche Evolutionswege zusammenlaufen.
Abstract
Phylogenetic diversity is a measure used to quantify the biodiversity of a set of species. Here, we introduce the average-tree phylogenetic diversity score in rooted binary phylogenetic networks and consider algorithms for computing and maximizing the score on a given network. Basically, the score is the weighted average of the phylogenetic diversity scores in all trees displayed by the network, with the weights determined by the inheritance probabilities on the reticulation edges used in the embeddings. We show that computing the score of a given set of taxa in a given network is #P-hard, directly implying #P-hardness of finding a subset of \(k\) taxa achieving maximum diversity score and thereby ruling out polynomial-time algorithms for these problems unless the polynomial hierarchy collapses. However, we show that both problems can be solved efficiently if the input network is close to being a tree in the sense that its reticulation number is small. More precisely, we prove that we can solve the optimization problem in networks with \(n\) leaves and \(r\) reticulations in \(2^{\mathcal{O}(r)} \cdot n \cdot k\) time. Using experiments on data produced by simulating a reticulate-evolution process, we show that our algorithm runs efficiently on networks with hundreds of taxa and tens of reticulations.
@inproceedings{vanIersel2025averagetree,
title = {{Average-Tree Phylogenetic Diversity of Networks}},
author = {van Iersel, Leo and Jones, Mark and Schestag, Jannik and Scornavacca, Celine and Weller, Mathias},
booktitle = {Proceedings of the 25th International Conference on Algorithms in Bioinformatics (WABI 2025)},
pages = {15:1--15:20},
year = {2025},
organization = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.WABI.2025.15}
}
[10]
Phylogenetic Network Diversity Parameterized by Reticulation Number and Beyond
Leo van Iersel,
Mark Jones,
Jannik Schestag,
Celine Scornavacca, and
Mathias Weller
Proceedings of the 22nd RECOMB International Workshop on Comparative Genomics (RECOMB-CG 2025)
In terms of laymen
Evolutionary networks allow several possible histories for a species, for example because of hybridization, and these histories may have different probabilities. This paper shows that selecting a maximally diverse group of species can be done efficiently when the number of such evolutionary merging events is small. Another, related, seemingly natural measure of network simplicity does not suffice.
In Laiensprache (German translation)
Evolutionäre Netzwerke erlauben mehrere mögliche Abstammungsgeschichten für eine Art, beispielsweise aufgrund von Hybridisierungen, und diese Geschichten können unterschiedliche Wahrscheinlichkeiten haben. Diese Arbeit zeigt, dass sich eine möglichst vielfältige Gruppe von Arten effizient auswählen lässt, wenn die Anzahl solcher evolutionären Verschmelzungsereignisse klein ist. Ein anderes, verwandtes, zunächst naheliegend erscheinendes Maß für die Einfachheit eines Netzwerks reicht dafür dagegen nicht aus.
Abstract
Network Phylogenetic Diversity (Network-PD) is a measure for the diversity of a set of species based on a rooted phylogenetic network (with branch lengths and inheritance probabilities on the reticulation edges) describing the evolution of those species. We consider the Maximize Network-PD problem: Given such a network, find \(k\) species with maximum Network-PD score. We show that this problem is fixed-parameter tractable (FPT) for binary networks, by describing an optimal algorithm running in \(\mathcal{O}(2^r \log(k)(n+r))\) time, with \(n\) the total number of species in the network and \(r\) its reticulation number. Furthermore, we show that Maximize Network-PD is NP-hard for level-1 networks, proving that, unless P=NP, the FPT approach cannot be extended by using the level as parameter instead of the reticulation number.
@inproceedings{vanIersel2025phylogenetic,
title = {{Phylogenetic Network Diversity Parameterized by Reticulation Number and Beyond}},
author = {van Iersel, Leo and Jones, Mark and Schestag, Jannik and Scornavacca, Celine and Weller, Mathias},
booktitle = {Proceedings of the 22nd RECOMB International Workshop on Comparative Genomics (RECOMB-CG 2025)},
pages = {107--130},
year = {2025},
organization = {Springer},
doi = {10.1007/978-3-031-94928-9_7}
}
2024
[9]
Maximizing Phylogenetic Diversity under Ecological Constraints: A Parameterized Complexity Study
Christian Komusiewicz and
Jannik Schestag
Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)
In terms of laymen
Saving an evolutionarily diverse group of species is of little use if some of those species cannot survive because the prey they need has disappeared. This paper studies conservation choices that simultaneously preserve evolutionary diversity and respect such ecological dependencies, and identifies several kinds of ecosystem structure that make the problem efficiently solvable.
In Laiensprache (German translation)
Eine evolutionär vielfältige Gruppe von Arten zu schützen, hilft wenig, wenn einige dieser Arten nicht überleben können, weil die von ihnen benötigten Beutetiere verschwunden sind. Diese Arbeit untersucht Schutzentscheidungen, die gleichzeitig evolutionäre Vielfalt bewahren und solche ökologischen Abhängigkeiten berücksichtigen. Sie zeigt mehrere Arten von Ökosystemstrukturen auf, unter denen sich das Problem effizient lösen lässt.
Abstract
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\({}_{\text{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\({}_{\text{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\({}_{\text{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\({}_{\text{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\({}_{\text{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\({}_{\text{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}
}
[8]
Protective and Nonprotective Subset Sum Games: A Parameterized Complexity Analysis
Jaroslav Garvardt,
Christian Komusiewicz,
Ber Lorke, and
Jannik Schestag
Proceedings of the 8th International Conference on Algorithmic Decision Theory (ADT 2024)
In terms of laymen
Two players take turns putting their own weighted items into a shared knapsack, with one player trying to reach a target while the other may either behave greedily or actively try to prevent this. This paper investigates how difficult it is to find a winning strategy under different rules and also considers a semi-cooperative “protective” version in which the first player wants the second player to reach a target as well.
In Laiensprache (German translation)
Zwei Spieler legen abwechselnd ihre jeweils unterschiedlich gewichteten Gegenstände in einen gemeinsamen Rucksack. Dabei versucht ein Spieler, einen bestimmten Zielwert zu erreichen, während der andere entweder eigennützig handelt oder dies aktiv verhindern möchte. Diese Arbeit untersucht, wie schwierig es unter verschiedenen Regeln ist, eine Gewinnstrategie zu finden, und betrachtet außerdem eine halbkooperative Variante, bei der der erste Spieler auch dem zweiten helfen möchte, dessen Ziel zu erreichen.
Abstract
In Subset Sum Game as studied by Pieterse and Woeginger [Theory of Computing Systems, 2021], two players alternatingly fill a common knapsack each with items from a private collection. The goal of Player A is to reach a value of at least \(T_A\), whereas Player B may follow different strategies. Subset Sum Game is NP-complete and solvable in pseudopolynomial time if Player B greedily selects the biggest available item in each turn; the game is PSPACE-complete, however, if Player B plays a hostile strategy where the only aim is to avoid that Player A wins. We continue the study of the game with these two strategies for Player B.
First, we provide a faster pseudopolynomial-time algorithm for a greedy Player B and show that the problem with a hostile Player B is fixed-parameter tractable with respect to the knapsack capacity \(C\). Moreover, we study the influence of further parameters such as \(T_A\), the number of rounds in the game, and the number of different numbers in the input on the complexity of the problem. Second, we consider a further variant of the game, called Protective Subset Sum Game, where Player A additionally has the goal that Player B reaches a value of at least \(T_B\). In a nutshell, we show that most algorithms for the nonprotective variant can be transferred to Protective Subset Sum Game.
First, we provide a faster pseudopolynomial-time algorithm for a greedy Player B and show that the problem with a hostile Player B is fixed-parameter tractable with respect to the knapsack capacity \(C\). Moreover, we study the influence of further parameters such as \(T_A\), the number of rounds in the game, and the number of different numbers in the input on the complexity of the problem. Second, we consider a further variant of the game, called Protective Subset Sum Game, where Player A additionally has the goal that Player B reaches a value of at least \(T_B\). In a nutshell, we show that most algorithms for the nonprotective variant can be transferred to Protective Subset Sum Game.
@inproceedings{garvardt2024protective,
title = {{Protective and Nonprotective Subset Sum Games: A Parameterized Complexity Analysis}},
author = {Garvardt, Jaroslav and Komusiewicz, Christian and Lorke, Ber and Schestag, Jannik},
booktitle = {Proceedings of the 8th International Conference on Algorithmic Decision Theory (ADT 2024)},
pages = {82--97},
year = {2024},
organization = {Springer},
doi = {10.1007/978-3-031-73903-3_6}
}
[7]
Maximizing Phylogenetic Diversity under Time Pressure: Planning with Extinctions Ahead
Mark Jones and
Jannik Schestag
In terms of laymen
Conservation takes time: Protecting a species may require a lengthy project, while the species itself may become extinct if help arrives too late. This paper treats conservation as a scheduling problem for one or more teams and investigates when good plans can be found efficiently despite these deadlines.
In Laiensprache (German translation)
Artenschutz benötigt Zeit: Der Schutz einer Art kann ein länger dauerndes Projekt erfordern, während die Art selbst aussterben könnte, wenn die Hilfe zu spät kommt. Diese Arbeit betrachtet Artenschutz deshalb als Planungsproblem für ein oder mehrere Teams und untersucht, unter welchen Bedingungen sich trotz solcher Fristen effiziente Schutzpläne finden lassen.
Abstract
Phylogenetic Diversity (PD) is a measure of the overall biodiversity of a set of present-day species (taxa) within a phylogenetic tree. In Maximize Phylogenetic Diversity (MPD) one is asked to find a set of taxa (of bounded size/cost) for which this measure is maximized. MPD is a relevant problem in conservation planning, where there are not enough resources to preserve all taxa and minimizing the overall loss of biodiversity is critical. We consider an extension of this problem, motivated by real-world concerns, in which each taxon not only requires a certain amount of time to save, but also has an extinction time after which it can no longer be saved. In addition there may be multiple teams available to work on preservation efforts in parallel; we consider two variants of the problem based on whether teams are allowed to collaborate on the same taxa. These problems have much in common with machine scheduling problems, (with taxa corresponding to tasks and teams corresponding to machines), but with the objective function (the phylogenetic diversity) inspired by biological considerations. Our extensions are, in contrast to the original MPD, NP-hard, even in very restricted cases. We provide several algorithms and hardness-results and thereby show that the problems are fixed-parameter tractable (FPT) when parameterized the target phylogenetic diversity, and that the problem where teams are allowed to collaborate is FPT when parameterized the acceptable loss of diversity.
@article{jones2024maximizing,
title = {{Maximizing Phylogenetic Diversity under Time Pressure: Planning with Extinctions Ahead}},
author = {Jones, Mark and Schestag, Jannik},
year = {2024},
archivePrefix = {arXiv},
journal = {arXiv preprint},
eprint = {2403.14217}
}
[6]
On Critical Node Problems with Vulnerable Vertices
Jannik Schestag,
Niels Grüttemeier,
Christian Komusiewicz, and
Frank Sommer
In terms of laymen
In some networks, particular vertices are especially important or vulnerable, and one may want to isolate them from as much of the remaining network as possible by removing only a few vertices. This paper studies two versions of that problem and determines a range of conditions under which it can be solved efficiently, as well as cases that remain computationally difficult.
In Laiensprache (German translation)
In manchen Netzwerken sind bestimmte Knoten besonders wichtig oder gefährdet. Dann kann das Ziel darin bestehen, diese durch das Entfernen möglichst weniger anderer Knoten von einem möglichst großen Teil des restlichen Netzwerks abzutrennen. Diese Arbeit untersucht zwei Varianten dieses Problems und bestimmt sowohl Bedingungen, unter denen es effizient gelöst werden kann, als auch Fälle, die rechnerisch schwierig bleiben.
Abstract
A vertex pair in an undirected graph is called connected if the two vertices are connected by a path. In the NP-hard Critical Node Problem (CNP), the input is an undirected graph \(G\) with integers \(k\) and \(x\), and the question is whether one can transform \(G\) by deleting at most \(k\) vertices into a graph whose total number of connected vertex pairs is at most \(x\). In this work, we introduce and study two NP- hard variants of CNP where a subset of the vertices is marked as vulnerable, and we aim to obtain a graph with at most \(x\) connected vertex pairs containing at least one vulnerable vertex. In the first variant, which generalizes CNP, we may delete vulnerable and non-vulnerable vertices. In the second variant, we may only delete non-vulnerable vertices.
We perform a parameterized complexity study of both problems. For example, we show that both problems are FPT with respect to \(k + x\). Furthermore, in the case of deletable vulnerable nodes, we provide a polynomial kernel for the parameter \(vc +k\), where \(vc\) is the vertex cover number. In the case of non-deletable vulnerable nodes, we prove NP-hardness even when there is only one vulnerable node.
We perform a parameterized complexity study of both problems. For example, we show that both problems are FPT with respect to \(k + x\). Furthermore, in the case of deletable vulnerable nodes, we provide a polynomial kernel for the parameter \(vc +k\), where \(vc\) is the vertex cover number. In the case of non-deletable vulnerable nodes, we prove NP-hardness even when there is only one vulnerable node.
@article{schestag2024critical,
title = {{On Critical Node Problems with Vulnerable Vertices}},
author = {Schestag, Jannik and Gruettemeier, Niels and Komusiewicz, Christian and Sommer, Frank},
journal = {Journal of Graph Algorithms and Applications},
volume = {28},
number = {1},
pages = {1--26},
year = {2024},
doi = {10.7155/jgaa.v28i1.2922}
}
2023
[5]
Finding Degree-Constrained Acyclic Orientations
Jaroslav Garvardt,
Malte Renken,
Jannik Schestag, and
Mathias Weller
Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
In terms of laymen
Sometimes the connections of an undirected network need to be assigned directions while obeying local restrictions on how many connections may point into each vertex, and without creating any directed cycles. This paper shows that this task is difficult in general but can be solved efficiently in important cases arising from evolutionary networks when the underlying structure or the number of ambiguous choices is sufficiently simple.
In Laiensprache (German translation)
Manchmal müssen den Verbindungen eines ungerichteten Netzwerks Richtungen zugewiesen werden, wobei für jeden Knoten Einschränkungen gelten, wie viele Verbindungen auf ihn zeigen dürfen, und gleichzeitig keine gerichteten Kreise entstehen sollen. Diese Arbeit zeigt, dass diese Aufgabe im Allgemeinen schwierig ist, sich aber in wichtigen Fällen aus dem Bereich evolutionärer Netzwerke effizient lösen lässt, wenn die zugrundeliegende Struktur oder die Anzahl mehrdeutiger Entscheidungen hinreichend einfach ist.
Abstract
We consider the problem of orienting a given, undirected graph into a (directed) acyclic graph such that the in-degree of each vertex \(v\) is in a prescribed list \(\lambda(v)\). Variants of this problem have been studied for a long time and with various applications, but mostly without the requirement for acyclicity. Without this requirement, the problem is closely related to the classical General Factor problem, which is known to be NP-hard in general, but polynomial-time solvable if no list \(\lambda(v)\) contains large “gaps” [Cornuéjols, J. Comb. Theory B, 1988]. In contrast, we show that deciding if an acyclic orientation exists is NP-hard even in the absence of such “gaps”.
On the positive side, we design parameterized algorithms for various, natural parameterizations of the acyclic orientation problem. A special case of the orientation problem with degree constraints recently came up in the context of reconstructing evolutionary histories (that is, phylogenetic networks). This phylogenetic setting imposes additional structure onto the problem that can be exploited algorithmically, allowing us to show fixed-parameter tractability when parameterized by either the treewidth of \(G\) (a smaller parameter than the frequently employed “level”), by the number of vertices \(v\) for which \(|\lambda(v)| \geq 2\), by the number of vertices \(v\) for which the highest value in \(\lambda(v)\) is at least 2. While the latter result can be extended to the general degree-constraint acyclic orientation problem, we show that the former cannot unless FPT=W[1].
On the positive side, we design parameterized algorithms for various, natural parameterizations of the acyclic orientation problem. A special case of the orientation problem with degree constraints recently came up in the context of reconstructing evolutionary histories (that is, phylogenetic networks). This phylogenetic setting imposes additional structure onto the problem that can be exploited algorithmically, allowing us to show fixed-parameter tractability when parameterized by either the treewidth of \(G\) (a smaller parameter than the frequently employed “level”), by the number of vertices \(v\) for which \(|\lambda(v)| \geq 2\), by the number of vertices \(v\) for which the highest value in \(\lambda(v)\) is at least 2. While the latter result can be extended to the general degree-constraint acyclic orientation problem, we show that the former cannot unless FPT=W[1].
@inproceedings{garvardt2023finding,
title = {{Finding Degree-Constrained Acyclic Orientations}},
author = {Garvardt, Jaroslav and Renken, Malte and Schestag, Jannik and Weller, Mathias},
booktitle = {Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {19:1--19:14},
year = {2023},
organization = {Schloss-Dagstuhl-Leibniz Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.IPEC.2023.19}
}
[4]
On the Complexity of Finding a Sparse Connected Spanning Subgraph in a Non-Uniform Failure Model
Matthias Bentert,
Jannik Schestag, and
Frank Sommer
Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
In terms of laymen
Imagine designing a sparse network in which some connections are reliable and others may fail, while requiring that the whole network remains connected if any one unreliable connection breaks. This paper investigates when such a robust network can be found efficiently and gives a broad classification of which structural properties make the task manageable.
In Laiensprache (German translation)
Man stelle sich vor, ein möglichst sparsames Netzwerk zu entwerfen, in dem einige Verbindungen zuverlässig sind und andere ausfallen können. Gleichzeitig soll das gesamte Netzwerk auch dann verbunden bleiben, wenn eine einzelne unzuverlässige Verbindung ausfällt. Diese Arbeit untersucht, wann sich ein solches robustes Netzwerk effizient finden lässt, und klassifiziert umfassend, welche strukturellen Eigenschaften die Aufgabe beherrschbar machen.
Abstract
We study a generalization of the classic Spanning Tree problem that allows for a non-uniform failure model. More precisely, edges are either safe or unsafe and we assume that failures only affect unsafe edges. In Unweighted Flexible Graph Connectivity we are given an undirected graph \(G = (V,E)\) in which the edge set \(E\) is partitioned into a set \(S\) of safe edges and a set \(U\) of unsafe edges and the task is to find a set \(T\) of at most \(k\) edges such that \(T - u\) is connected and spans \(V\) for any unsafe edge \(u \in T\). Unweighted Flexible Graph Connectivity generalizes both Spanning Tree and Hamiltonian Cycle. We study Unweighted Flexible Graph Connectivity in terms of fixed-parameter tractability (FPT). We show an almost complete dichotomy on which parameters lead to fixed-parameter tractability and which lead to hardness. To this end, we obtain FPT-time algorithms with respect to the vertex deletion distance to cluster graphs and with respect to the treewidth. By exploiting the close relationship to Hamiltonian Cycle, we show that FPT-time algorithms for many smaller parameters are unlikely under standard parameterized complexity assumptions. Regarding problem-specific parameters, we observe that Unweighted Flexible Graph Connectivity admits an FPT-time algorithm when parameterized by the number of unsafe edges. Furthermore, we investigate a below-upper-bound parameter for the number of edges of a solution. We show that this parameter also leads to an FPT-time algorithm.
@inproceedings{bentert2023complexity,
title = {{On the Complexity of Finding a Sparse Connected Spanning Subgraph in a Non-Uniform Failure Model}},
author = {Bentert, Matthias and Schestag, Jannik and Sommer, Frank},
booktitle = {Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {4:1--4:12},
year = {2023},
organization = {Schloss-Dagstuhl-Leibniz Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.IPEC.2023.4}
}
[3]
Maximizing All-Paths Phylogenetic Diversity: Parameterized Approaches for Networks
Mark Jones and
Jannik Schestag
Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)
In terms of laymen
Evolution is not always well represented by a tree because events such as hybridization can create several ancestral routes to the same species. This paper studies how to select a small group of species that preserves as much of such an evolutionary network as possible. The problem is computationally difficult in general but becomes efficiently solvable when certain reasons of network complexity are limited.
In Laiensprache (German translation)
Evolution lässt sich nicht immer angemessen durch einen Baum darstellen, da Ereignisse wie Hybridisierungen dazu führen können, dass eine Art über mehrere Abstammungswege erreicht wird. Diese Arbeit untersucht, wie man eine kleine Gruppe von Arten auswählen kann, die möglichst viel eines solchen evolutionären Netzwerks bewahrt. Das Problem ist im Allgemeinen schwierig zu berechnen, kann aber effizient gelöst werden, wenn bestimmte Ursachen der Netzwerkkomplexität begrenzt sind.
Abstract
Phylogenetic Diversity (PD) is a fundamental measure of biodiversity, originally defined on phylogenetic trees and widely used in conservation biology. Phylogenetic trees are often generalised to directed acyclic graphs, called phylogenetic networks. As such, a corresponding generalization of PD is needed. A natural generalization to edge-weighted phylogenetic networks is the all-paths measure, where the diversity of a set \(S\) of species (taxa) is defined as the total weight of all edges that lie on a path from the root to at least one species in \(S\). While maximizing PD on trees can be solved in polynomial time, the corresponding problem on networks is NP-hard and difficult to approximate. We undertake a systematic parameterized complexity study of the Max-All-Paths-PD (MapPD) problem. We establish W[2]-hardness when parameterized by the number of species that are included in a solution, and W[1]-hardness for the number of species that are excluded. On the positive side, we show that the problem is fixed-parameter tractable with respect to the threshold of diversity and the acceptable loss of diversity. We further analyze how the network's proximity to a tree influences algorithmic behavior and present single-exponential fixed-parameter algorithms when parameterized by the number of reticulations and by the treewidth of the underlying graph. Finally, we present a polynomial kernelization for MapPD with respect to the number of reticulation edges.
@inproceedings{jones2023maximize,
title = {{How Can We Maximize Phylogenetic Diversity? Parameterized Approaches for Networks}},
author = {Jones, Mark and Schestag, Jannik},
booktitle = {Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
pages = {30:1--30:12},
year = {2023},
organization = {Schloss-Dagstuhl-Leibniz Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.IPEC.2023.30}
}
[2]
On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem
Christian Komusiewicz,
Simone Linz,
Nils Morawietz, and
Jannik Schestag
Proceedings of the 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)
In terms of laymen
A common method for reconstructing an evolutionary tree is to start with a candidate tree and repeatedly make small changes that improve how well it explains the observed biological data. This paper shows that for several standard kinds of tree modification, checking all nearby alternatives is essentially unavoidable in the worst case, while a more restricted form of modification permits a substantially faster search.
In Laiensprache (German translation)
Eine verbreitete Methode zur Rekonstruktion eines Evolutionsbaums besteht darin, mit einem möglichen Baum zu beginnen und ihn schrittweise so zu verändern, dass er die beobachteten biologischen Daten besser erklärt. Diese Arbeit zeigt, dass bei mehreren üblichen Arten solcher Veränderungen im schlimmsten Fall im Wesentlichen alle naheliegenden Alternativen geprüft werden müssen. Für eine stärker eingeschränkte Form der Veränderung ist dagegen eine wesentlich schnellere Suche möglich.
Abstract
Maximum Parsimony is the problem of computing a most parsimonious phylogenetic tree for a taxa set \(X\) from character data for \(X\). A common strategy to attack this notoriously hard problem is to perform a local search over the phylogenetic tree space. Here, one is given a phylogenetic tree \(T\) and wants to find a more parsimonious tree in the neighborhood of \(T\). We study the complexity of this problem when the neighborhood contains all trees within distance \(k\) for several classic distance functions. For the nearest neighbor interchange (NNI), subtree prune and regraft (SPR), tree bisection and reconnection (TBR), and edge contraction and refinement (ECR) distances, we show that, under the exponential time hypothesis, there are no algorithms with running time \(|I|^{o(k)}\) where \(|I|\) is the total input size. Hence, brute-force algorithms with running time \(|X|^{\mathcal{O}(k)} \cdot |I|\) are essentially optimal.
In contrast to the above distances, we observe that for the sECR-distance, where the contracted edges are constrained to form a subtree, a better solution within distance \(k\) can be found in \(k^{\mathcal{O}(k)} \cdot |I|^{\mathcal{O}(1)}\) time.
In contrast to the above distances, we observe that for the sECR-distance, where the contracted edges are constrained to form a subtree, a better solution within distance \(k\) can be found in \(k^{\mathcal{O}(k)} \cdot |I|^{\mathcal{O}(1)}\) time.
@inproceedings{komusiewicz2023complexity,
title = {{On the Complexity of Parameterized Local Search for the Maximum Parsimony Problem}},
author = {Komusiewicz, Christian and Linz, Simone and Morawietz, Nils and Schestag, Jannik},
booktitle = {Proceedings of the 34th Annual Symposium on Combinatorial Pattern Matching (CPM 2023)},
pages = {18:1--18:18},
year = {2023},
organization = {Schloss-Dagstuhl-Leibniz Zentrum f{\"u}r Informatik},
doi = {10.4230/LIPIcs.CPM.2023.18}
}
2021
[1]
Destroying Bicolored \(P_3\)s by Deleting Few Edges
Niels Grüttemeier,
Christian Komusiewicz,
Jannik Schestag, and
Frank Sommer
In terms of laymen
Consider a network whose connections are colored red or blue, and suppose we want to remove only a few connections so that no path through three vertices uses both colors. This paper shows that finding such a small set of deletions is difficult in general, but gives faster algorithms, useful preprocessing techniques, and special graph classes on which the problem can be solved efficiently.
In Laiensprache (German translation)
Betrachten wir ein Netzwerk, dessen Verbindungen rot oder blau gefärbt sind. Gesucht sind möglichst wenige Verbindungen, die entfernt werden müssen, sodass kein Pfad über drei Knoten mehr beide Farben verwendet. Diese Arbeit zeigt, dass das Finden einer solchen kleinen Menge im Allgemeinen schwierig ist, entwickelt aber schnellere Algorithmen und nützliche Vorverarbeitungstechniken und identifiziert spezielle Netzwerkklassen, für die sich das Problem effizient lösen lässt.
Abstract
We introduce and study the Bicolored \(P_3\) Deletion problem defined as follows. The input is a graph \(G = (V, E)\) where the edge set \(E\) is partitioned into a set \(E_r\) of red edges and a set \(E_b\) of blue edges. The question is whether we can delete at most \(k\) edges such that \(G\) does not contain a bicolored \(P_3\) as an induced subgraph. Here, a bicolored \(P_3\) is a path on three vertices with one blue and one red edge. We show that Bicolored \(P_3\) Deletion is NP-hard and cannot be solved in \(2^{o(|V|+|E|)}\) time on bounded-degree graphs if the ETH is true. Then, we show that Bicolored \(P_3\) Deletion is polynomial-time solvable when \(G\) does not contain a bicolored \(K_3\), that is, a triangle with edges of both colors. We also provide a polynomial-time algorithm for the case that \(G\) contains no blue \(P_3\), red \(P_3\), blue \(K_3\), and red \(K_3\). Finally, we show that Bicolored \(P_3\) Deletion can be solved in \(\mathcal{O}(1.84^k \cdot |V | \cdot |E|)\) time and that it admits a kernel with \(\mathcal{O}(k \Delta \min(k, \Delta))\) vertices, where \(\Delta\) is the maximum degree of \(G\).
@article{gruttemeier2021destroying,
title = {{Destroying Bicolored P3s by Deleting Few Edges}},
author = {Gr{\"u}ttemeier, Niels and Komusiewicz, Christian and Schestag, Jannik and Sommer, Frank},
journal = {Discrete Mathematics \& Theoretical Computer Science},
volume = {23},
number = {1},
year = {2021},
publisher = {Episciences.org},
doi = {10.46298/dmtcs.6108}
}