Non-essential arcs in phylogenetic networks

Abstract

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}}^{\prime }$ such that the sets of rooted phylogenetic trees that are embedded in $\mathcal{N}$ and ${\mathcal{N}}^{\prime }$ 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.

References in corpus (2)

• Displaying trees across two phylogenetic networks
• Display sets of normal and tree-child networks

Cited by in corpus (1)

• Hypercubes and Hamilton cycles of display sets of rooted phylogenetic networks