On the computational complexity of the rooted subtree prune and regraft distance
The paper proves that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic trees on the same label set is NP-hard -- solving a longstanding problem. (This operation cuts off a subtree and reattaches it to another part of the tree.)
scientific article; zbMATH DE number 2138552
scientific article