Rooted Almost-binary Phylogenetic Networks for which the Maximum Covering Subtree Problem is Solvable in Linear Time
share
Phylogenetic networks are a flexible model of evolution that can represent reticulate evolution and handle complex data. Tree-based networks, which are phylogenetic networks that have a spanning tree with the same root and leaf-set as the network itself, have been well studied. However, not all networks are tree-based. Francis-Semple-Steel (2018) thus introduced several indices to measure the deviation of rooted binary phylogenetic networks N from being tree-based, such as the minimum number δ^∗(N) of additional leaves needed to make N tree-based, and the minimum difference η^∗(N) between the number of vertices of N and the number of vertices of a subtree of N that shares the root and leaf set with N. Hayamizu (2021) has established a canonical decomposition of almost-binary phylogenetic networks of N, called the maximal zig-zag trail decomposition, which has many implications including a linear time algorithm for computing δ^∗(N). The Maximum Covering Subtree Problem (MCSP) is the problem of computing η^∗(N), and Davidov et al. (2022) showed that this can be solved in polynomial time (in cubic time when N is binary) by an algorithm for the minimum cost flow problem. In this paper, under the assumption that N is almost-binary (i.e. each internal vertex has in-degree and out-degree at most two), we show that δ^∗(N)≤η^∗ (N) holds, which is tight, and give a characterisation of such phylogenetic networks N that satisfy δ^∗(N)=η^∗(N). Our approach uses the canonical decomposition of N and focuses on how the maximal W-fences (i.e. the forbidden subgraphs of tree-based networks) are connected to maximal M-fences in the network N. Our results introduce a new class of phylogenetic networks for which MCSP can be solved in linear time, which can be seen as a generalisation of tree-based networks.
READ FULL TEXT