Orienting Unrooted Binary Networks Faster: Focus on the Generator
This work provides faster algorithms for a core NP-hard problem in phylogenetics, benefiting researchers who need to construct rooted phylogenetic networks from unrooted data.
The authors introduce two algorithmic frameworks that yield fixed-parameter tractable algorithms for orienting unrooted binary networks into rooted phylogenetic networks, parameterized by network level ℓ. Their methods achieve running times such as O(5.3334^ℓ ⋅ n) for tree-based networks and O(12.2071^ℓ ⋅ n^2) for temporal networks, significantly improving best-known results.
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 $O(5.3334^\ell + \ell)$ time and orienting all remaining edges in polynomial time, we solve the orientation problem in $O(5.3334^\ell \cdot n)$ time for tree-based networks and in $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 $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 $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.