{"ID":2900959,"CreatedAt":"2026-06-01T05:51:17.9442275Z","UpdatedAt":"2026-06-01T09:30:02.809313052Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2605.31071","arxiv_id":"2605.31071","title":"Tree Containment Parameterized by Scanwidth","abstract":"TREE 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$.","short_abstract":"TREE 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...","url_abs":"https://arxiv.org/abs/2605.31071","url_pdf":"https://arxiv.org/pdf/2605.31071v1","authors":"[\"Leo van Iersel\",\"Mark Jones\",\"Mathias Weller\"]","published":"2026-05-29T09:38:57Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"cs.CC\",\"q-bio.PE\"]","methods":"[]","has_code":false}