On the computational complexity of the rooted subtree prune and regraft distance

Bordewich, M.; Semple, C.

Abstract

The graph-theoretic operation of rooted subtree prune and regraft is increasingly being used as a tool for understanding and modelling reticulation events in evolutionary biology. In this paper, we show that computing the rooted subtree prune and regraft distance between two rooted binary phylogenetic trees on the same label set is NP-hard. This resolves a longstanding open problem. Furthermore, we show that this distance is xed parameter tractable when parameterised by the distance between the two trees.

Citation

Bordewich, M., & Semple, C. (2005). On the computational complexity of the rooted subtree prune and regraft distance. Annals of Combinatorics, 8(4), 409-423. https://doi.org/10.1007/s00026-004-0229-z

• Journal Article Type: Article
• Publication Date: 2005-01
• Deposit Date: Oct 13, 2008
• Publicly Available Date: Oct 13, 2008
• Journal: Annals of Combinatorics
• Print ISSN: 0218-0006
• Electronic ISSN: 0219-3094
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 8
• Issue: 4
• Pages: 409-423
• DOI: https://doi.org/10.1007/s00026-004-0229-z
• Keywords: Rooted phylogenetic tree, Rooted subtree prune, Regraft.
• Public URL: https://durham-repository.worktribe.com/output/1565450
• Publisher URL: http://www.springerlink.com/openurl.asp?genre=article&eissn=0219-3094&volume=8&issue=4&spage=409