{"ID":5438865,"CreatedAt":"2026-07-01T01:17:58.482524686Z","UpdatedAt":"2026-07-03T12:44:19.017960396Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.31597","arxiv_id":"2606.31597","title":"Orienting Unrooted Binary Networks Faster: Focus on the Generator","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 $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.","short_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...","url_abs":"https://arxiv.org/abs/2606.31597","url_pdf":"https://arxiv.org/pdf/2606.31597v1","authors":"[\"Jannik Schestag\",\"Norbert Zeh\"]","published":"2026-06-30T12:44:34Z","proceeding":"cs.DS","tasks":"[\"cs.DS\"]","methods":"[]","has_code":false}