On the Maximum Agreement Subtree Conjecture for Balanced Trees

DOI10.1137/20M1379678MaRDI QIDQ5028359zbMATH OpenOpenAlexWikidataFDO

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

Publication date 9 February 2022

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2005.07357

zbMATH Keywords

phylogenetic treemaximum agreement subtreebalanced treecatepillar

Mathematics Subject Classification ID

Problems related to evolution (92D15) Trees (05C05)

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^{frac12}$. 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 $c{n}^{frac12}$. We also improve the lower bound of the size of such a MAST to $n^{frac16}$.

Recommendations

• On the extremal maximum agreement subtree problem
• An improved bound on the maximum agreement subtree problem
• On the approximability of the maximum agreement subtree and maximum compatible tree problems
• The maximum agreement subtree problem
• Solving the Maximum Agreement SubTree and the Maximum Compatible Tree Problems on Many Bounded Degree Trees
• Bounds on the expected size of the maximum agreement subtree for a given tree shape
• Bounds on the expected size of the maximum agreement subtree
• scientific article; zbMATH DE number 1974592
• scientific article; zbMATH DE number 434699
• scientific article; zbMATH DE number 871929

Cites work

• scientific article; zbMATH DE number 1974592 (Why is no real title available?)
• scientific article; zbMATH DE number 1974599 (Why is no real title available?)
• scientific article; zbMATH DE number 1865935 (Why is no real title available?)
• An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees
• An improved bound on the maximum agreement subtree problem
• Bounds on the expected size of the maximum agreement subtree
• Bounds on the expected size of the maximum agreement subtree for a given tree shape
• Kaikoura tree theorems: Computing the maximum agreement subtree
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• Maximum agreement and compatible supertrees
• On the extremal maximum agreement subtree problem
• The agreement metric for labeled binary trees
• The maximum agreement subtree problem

Cited in

(4)

• Expected Number of Induced Subtrees Shared by Two Independent Copies of a Random Tree
• An improved lower bound on the largest common subtree of random leaf-labeled binary trees
• On the extremal maximum agreement subtree problem
• The maximum agreement subtree problem

Describes a project that uses

Uses Software

• phangorn
• OEIS

This page was built for publication: On the Maximum Agreement Subtree Conjecture for Balanced Trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5028359)