Abstract
The problem of orienting an unrooted network is known to be NP-hard in many cases. This paper introduces two algorithmic frameworks that yield significantly improved fixed-parameter tractable (FPT) algorithms parameterized by the network level $l$. 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 $O(5.3334^l + l)$ time and orienting all remaining edges in polynomial time, we solve the orientation problem in $O(5.3334^l \times n)$ time for tree-based networks and in $O(5.3334^l \times n^2)$ time for orchards, where $n$ is the number of vertices of the graph. Extending this approach with further branching yields $O(10.6667^l \times 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 $O(12.2071^l \times 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.
Blogger's Review: This paper presents innovative algorithmic frameworks for the orientation problem of unrooted binary networks, particularly showcasing the efficiency of the reticulation-guessing technique. This offers a substantial theoretical foundation and practical guidance for tackling complex biological network issues, making it a valuable read for researchers in the field.