Non-essential arcs in phylogenetic networks

摘要

In the study of rooted phylogenetic networks, analyzing the set of rooted phylogenetic trees that are embedded in such a network is a recurring task. Algorithmically, this analysis requires a search of the exponential-sized multiset S of rooted phylogenetic trees that are embedded in a rooted phylogenetic network N. In this paper, we introduce the notion of a non-essential arc, which is an arc whose deletion from N results in a rooted phylogenetic network N′ that embeds the same set of rooted phylogenetic trees as N but whose associated multiset is smaller than S. We characterize non-essential arcs for the popular class of tree-child networks and show that identifying and deleting such arcs takes time that is cubic in the number of leaves of the network. Moreover, we show that deciding if a given arc of an arbitrary phylogenetic network is non-essential is Π2P-complete.