On the Maximum Agreement Subtree Conjecture for Balanced Trees

Bordewich, Magnus; Linz, Simone; Owen, Megan; St. John, Katherine; Semple, Charles; Wicke, Kristina

Abstract

We give a counterexample to the conjecture of Martin and Thatte that two balanced rooted binary leaf-labelled trees on n leaves have a maximum agreement subtree (MAST) of size at least n 1 2 . In particular, we show that for any c > 0, there exist two balanced rooted binary leaf-labelled trees on n leaves such that any MAST for these two trees has size less than cn 1 2 . We also improve the lower bound of the size of such a MAST to n 1 6 .

Citation

Bordewich, M., Linz, S., Owen, M., St. John, K., Semple, C., & Wicke, K. (2022). On the Maximum Agreement Subtree Conjecture for Balanced Trees. SIAM Journal on Discrete Mathematics, 36(1), 336-354. https://doi.org/10.1137/20m1379678

• Journal Article Type: Article
• Acceptance Date: Oct 15, 2021
• Online Publication Date: Jan 31, 2022
• Publication Date: 2022
• Deposit Date: Oct 27, 2021
• Publicly Available Date: Oct 27, 2021
• Journal: SIAM Journal on Discrete Mathematics
• Print ISSN: 0895-4801
• Electronic ISSN: 1095-7146
• Publisher: Society for Industrial and Applied Mathematics
• Peer Reviewed: Peer Reviewed
• Volume: 36
• Issue: 1
• Pages: 336-354
• DOI: https://doi.org/10.1137/20m1379678
• Public URL: https://durham-repository.worktribe.com/output/1225067