On the Maximum Agreement Subtree Conjecture for Balanced Trees

DOI10.1137/20M1379678zbMATH Open1482.05037arXiv2005.07357OpenAlexW3024252031WikidataQ113779065 ScholiaQ113779065MaRDI QIDQ5028359FDOQ5028359

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)

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}$.

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

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

zbMATH Keywords

phylogenetic treemaximum agreement subtreebalanced treecatepillar

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Kaikoura tree theorems: Computing the maximum agreement subtree
• Maximum agreement and compatible supertrees
• Title not available (Why is that?)
• Maximum Agreement Subtree in a Set of Evolutionary Trees: Metrics and Efficient Algorithms
• An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees
• An improved bound on the maximum agreement subtree problem
• The maximum agreement subtree problem
• The agreement metric for labeled binary trees
• Bounds on the expected size of the maximum agreement subtree
• On the extremal maximum agreement subtree problem
• Title not available (Why is that?)
• Bounds on the expected size of the maximum agreement subtree for a given tree shape

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

Uses Software

• OEIS
• phangorn

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)