{
  "$type": "site.standard.document",
  "bskyPostRef": {
    "cid": "bafyreieu467bfizgrm5k7f5a372xg54gspk3vmvhiveajbvx3yxbihwfgi",
    "uri": "at://did:plc:3fychdutjjusoqeq24ljch6q/app.bsky.feed.post/3mn7eedx4u4n2"
  },
  "coverImage": {
    "$type": "blob",
    "ref": {
      "$link": "bafkreiflo6xt7is6b2iafwghkjahlgggocme5jwjsbeuqqwcywuvjhmszm"
    },
    "mimeType": "image/png",
    "size": 24783
  },
  "path": "/abs/2605.31071v1",
  "publishedAt": "2026-06-01T00:00:00.000Z",
  "site": "https://arxiv.org",
  "tags": [
    "Leo van Iersel",
    "Mark Jones",
    "Mathias Weller"
  ],
  "textContent": "**Authors:** Leo van Iersel, Mark Jones, Mathias Weller\n\nTREE CONTAINMENT is a central decision problem in mathematical phylogenetics, asking whether a given rooted phylogenetic tree is embeddable in (\"displayed by\") a given rooted phylogenetic network. While the problem is NP-complete for general networks, many algorithmic advances have relied on structural parameters that capture how \"tree-like\" a network is. In this paper we investigate TREE CONTAINMENT under the structural parameter scanwidth, a directed width measure generalizing popular parameters measuring tree-likeness of phylogenetic networks. We first present a parameterized algorithm that solves the problem in $O(4^{k + k\\log{k}} n + nm^2)$ time, where $n$ and $m$ are the numbers of nodes and arcs in the network and $k$ is the width of a given tree-extension. Complementing this upper bound, we prove a matching lower bound under the Exponential-Time Hypothesis (ETH), showing that there is no algorithm for TREE CONTAINMENT that runs in $2^{o(c\\log{c})} n^{O(1)}$ time, even on binary inputs, where $c$ is the directed cutwidth of the input network, which upper-bounds the scanwidth $k$.",
  "title": "Tree Containment Parameterized by Scanwidth"
}