On the extremal maximum agreement subtree problem

DOI10.1016/J.DAM.2020.07.007zbMATH Open1447.05056arXiv1812.06951OpenAlexW3043286155MaRDI QIDQ2197478FDOQ2197478

Authors: Alexey Markin 

Publication date: 31 August 2020

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: Given two phylogenetic trees with the $1,ldots,n$ leaf-set the maximum agreement subtree problem asks what is the maximum size of the subset $Asubseteq1,ldots,n$ such that the two trees are equivalent when restricted to $A$. The long-standing extremal version of this problem focuses on the smallest number of leaves, $mathrmmast(n)$, on which any two (binary and unrooted) phylogenetic trees with $n$ leaves must agree. In this work we prove that this number grows asymptotically as $Theta(logn)$; thus closing the enduring gap between the lower and upper asymptotic bounds on $mathrmmast(n)$.

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

Recommendations

• The 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
• Solving the Maximum Agreement SubTree and the Maximum Compatible Tree Problems on Many Bounded Degree Trees
• An improved algorithm for the maximum agreement subtree problem
• On the Maximum Agreement Subtree Conjecture for Balanced Trees
• scientific article; zbMATH DE number 871929
• An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees
• Polynomial-time algorithms for the ordered maximum agreement subtree problem

zbMATH Keywords

lower boundphylogenetic treesmaximum agreement subtreelabeled trees

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35)

Cites Work

• Kaikoura tree theorems: Computing the maximum agreement subtree
• 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
• Bounds on the expected size of the maximum agreement subtree
• Title not available (Why is that?)
• Bounds on the expected size of the maximum agreement subtree for a given tree shape

Cited In (8)

• An \(O(n\log n)\) algorithm for the maximum agreement subtree problem for binary trees
• Bounds on the expected size of the maximum agreement subtree
• Expected Number of Induced Subtrees Shared by Two Independent Copies of a Random Tree
• On the Maximum Agreement Subtree Conjecture for Balanced Trees
• An improved lower bound on the largest common subtree of random leaf-labeled binary trees
• An improved bound on the maximum agreement subtree problem
• The maximum agreement subtree problem
• Maximum agreement subtrees and Hölder homeomorphisms between Brownian trees

This page was built for publication: On the extremal maximum agreement subtree problem

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