{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreibkhn4vyow375bbthy6zdvtwxz6u7z2fyrd5ff6quepgoscorngte",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mpleecyuuyj2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2606.31597v1",
  "publishedAt": "2026-07-01T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Jannik Schestag",
    "Norbert Zeh"
  ],
  "textContent": "**Authors:** Jannik Schestag, Norbert Zeh\n\nThe 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.",
  "title": "Orienting Unrooted Binary Networks Faster: Focus on the Generator"
}