On the Maximum Agreement Subtree Conjecture for Balanced Trees

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

doi:10.1137/20m1379678

On the Maximum Agreement Subtree Conjecture for Balanced Trees

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

Authors

Professor Magnus Bordewich m.j.r.bordewich@durham.ac.uk
Professor

Simone Linz

Megan Owen

Katherine St. John

Charles Semple

Kristina Wicke

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