Combining Orthology and Xenology Data in a Common Phylogenetic Tree

A rooted tree $T$ with vertex labels $t(v)$ and set-valued edge labels $lambda(e)$ defines maps $delta$ and $varepsilon$ on the pairs of leaves of $T$ by setting $delta(x,y)=q$ if the last common ancestor $text{lca}(x,y)$ of $x$ and $y$ is labeled $q$, and $min varepsilon(x,y)$ if $minlambda(e)$ for at least one edge $e$ along the path from $text{lca}(x,y)$ to $y$. We show that a pair of maps $(delta,varepsilon)$ derives from a tree $(T,t,lambda)$ if and only if there exists a common refinement of the (unique) least-resolved vertex labeled tree $(T_{delta},t_{delta})$ that explains $delta$ and the (unique) least resolved edge labeled tree $(T_{varepsilon},lambda_{varepsilon})$ that explains $varepsilon$ (provided both trees exist). This result remains true if certain combinations of labels at incident vertices and edges are forbidden.