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. From an algorithmic viewpoint, this analysis almost always requires an exhaustive search of a particular multiset $S$ of rooted phylogenetic trees that are embedded in a rooted phylogenetic network $mathcal{N}$. Since the size of $S$ is exponential in the number of reticulations of $mathcal{N}$, it is consequently of interest to keep this number as small as possible but without loosing any element of $S$. In this paper, we take a first step towards this goal by introducing the notion of a non-essential arc of $mathcal{N}$, which is an arc whose deletion from $mathcal{N}$ results in a rooted phylogenetic network $mathcal{N}$ such that the sets of rooted phylogenetic trees that are embedded in $mathcal{N}$ and $mathcal{N}$ are the same. We investigate the popular class of tree-child networks and characterize which arcs are non-essential. This characterization is based on a family of directed graphs. Using this novel characterization, we show that identifying and deleting all non-essential arcs in a tree-child network 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 $Pi_2^P$-complete.
Download