On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance
The graph-theoretic operation of rooted subtree prune and regraft is increasingly being used as a tool for understanding and modelling reticu- lation events in evolutionary biology. In this paper, we show that computing the rooted subtree prune and regraft distance between two rooted binary phy- logenetic trees on the same label set is NP-hard. This resolves a longstanding open problem. Furthermore, we show that this distance is fixed parameter tractable when parameterised by the distance between the two trees.