Average-Tree Phylogenetic Diversity Parameterized by Scanwidth and Invisibility
This work provides complexity classifications and efficient algorithms for a key biodiversity metric, benefiting computational phylogenetics by identifying tractable cases based on network structure.
The paper studies parameterized algorithms for computing average-tree phylogenetic diversity (APD) in rooted phylogenetic networks. It shows that APD can be computed in polynomial time for networks of scanwidth at most 2, but becomes NP-hard for scanwidth 3, and provides an O(2^{sw} n) algorithm for general scanwidth, as well as polynomial-time algorithms for reticulation-visible networks and networks with bounded invisible reticulations per biconnected component.
We investigate parameterized algorithms for computing the average-tree phylogenetic diversity (APD) in rooted phylogenetic networks, studying the problem under different structural parameters that capture the deviation of a network from a tree. Our primary parameter is the scanwidth, a measure of the tree-likeness of a given directed acyclic graph. We show that a subset of taxa with maximum APD can be found in polynomial time in phylogenetic networks of scanwidth at most 2, but becomes NP-hard in networks of scanwidth 3. Further, we design an algorithm that computes the APD of a given set of taxa in O(2^sw n) time, where sw denotes the scanwidth and n the number of taxa in the input network. Finally, we give a linear-time algorithm for computing the APD of a given set of taxa if the network induced by these taxa is reticulation-visible. We generalize this algorithm to still run in polynomial time if each biconnected component of the induced network has only constantly many invisible reticulations.