Testing the Agreement of Trees with Internal Labels

Abstract

The input to the agreement problem is a collection $P=\{T_1,T_2,\dots ,T_k\}$ of phylogenetic trees, called input trees, over partially overlapping sets of taxa. The question is whether there exists a tree $T$, called an agreement tree, whose taxon set is the union of the taxon sets of the input trees, such that for each $i\in \{1,2,\dots ,k\}$, the restriction of $T$ to the taxon set of $T_i$ is isomorphic to $T_i$. We give a $O(nk({\sum }_{i\in [k]}{d}_i+{\log }^2(nk)))$ algorithm for a generalization of the agreement problem in which the input trees may have internal labels, where $n$ is the total number of distinct taxa in $P$, $k$ is the number of trees in $P$, and $d_i$ is the maximum number of children of a node in $T_i$.