Orienting Publications

Below you can find my publications and preprints on Finding Orientations into Phylogeneitc Networks, with links and toggleable abstracts.
To filter by a certain topic, click one of the buttons.

Filter by topic All FPT Food Webs Orienting Phylogenetic Diversity Phylogenetic Networks Scanwidth Implemented Algorithms

2026

[2]

Orienting Unrooted Binary Networks Faster: Focus on the Generator

Jannik Schestag and Norbert Zeh

arXiv:2606.31597

Preprint

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}
}

2023

[1]

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)

Conference proceeding

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].

@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}
}