  Semi-labeled trees are phylogenies whose internal nodes may be labeled by
higher-order taxa. Thus, a leaf labeled Mus musculus could nest within a
subtree whose root node is labeled Rodentia, which itself could nest within a
subtree whose root is labeled Mammalia. Suppose we are given collection
$\mathcal P$ of semi-labeled trees over various subsets of a set of taxa. The
ancestral compatibility problem asks whether there is a semi-labeled tree
$\mathcal T$ that respects the clusterings and the ancestor/descendant
relationships implied by the trees in $\mathcal P$. We give a
$\tilde{O}(M_{\mathcal{P}})$ algorithm for the ancestral compatibility problem,
where $M_{\mathcal{P}}$ is the total number of nodes and edges in the trees in
$\mathcal P$. Unlike the best previous algorithm, the running time of our
method does not depend on the degrees of the nodes in the input trees.
