AI Insight
This paper investigates the computational complexity of the TREE CONTAINMENT problem in phylogenetics, which determines whether a phylogenetic tree can be embedded within a phylogenetic network. The authors present a parameterized algorithm that solves this NP-complete problem in O(4^(k + k log k) n + nm^2) time based on the scanwidth parameter, and prove a matching lower bound showing this exponential dependence on the parameter cannot be significantly improved under standard complexity assumptions. The results establish tight computational bounds for an important class of phylogenetic network analysis problems.
Why it matters
These findings provide both efficient algorithms and theoretical limitations for analyzing evolutionary relationships represented as phylogenetic networks, which are crucial tools in evolutionary biology for studying species with complex inheritance patterns like horizontal gene transfer or hybridization events.
arXiv:2605.31071v2 Announce Type: replace-cross
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 + klog{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(clog{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$.