Generalized Fitch Graphs II: Sets of Binary Relations that are explained by Edge-labeled Trees

Fitch graphs $G=(X,E)$ are digraphs that are explained by ${\emptyset, 1}$-edge-labeledrootedtrees$T$withleafset$X$:thereisanarc$(x,y) \in E$ifandonlyiftheuniquepathin$T$ that connects the last common ancestor $\mathrm{l}\mathrm{c}\mathrm{a}(x,y)$ of $x$ and $y$ with $y$ contains at least one edge with label “1”. In practice, Fitch graphs represent xenology relations, i.e., pairs of genes $x$ and $y$ for which a horizontal gene transfer happened along the path from $\mathrm{l}\mathrm{c}\mathrm{a}(x,y)$ to $y$. In this contribution, we generalize the concept of Fitch graphs and consider trees $T$ that are equipped with edge-labeling $\lambda :E\to \mathcal{P}(M)$ that assigns to each edge a subset $M^{\mathrm{\prime }}\subseteq M$ of colors. Given such a tree, we can derive a map ${\epsilon }_{(T,\lambda )}$ (or equivalently a set of not necessarily disjoint binary relations), such that $i\in \varepsilon_{(T,\lambda)}(x,y)$(orequivalently$(x,y)\in R_i$)with$x,y\in X$,ifandonlyifthereisatleastoneedgewithcolor$i$from$$\mathrm{l}\mathrm{c}\mathrm{a}$(x,y)$to$y$. The central question considered here: Is a given map $\epsilon$ a Fitch map, i.e., is there there an edge-labeled tree $(T,\lambda )$ with ${\epsilon }_{(T,\lambda )}=\epsilon$, and thus explains $\epsilon$? Here, we provide a characterization of Fitch maps in terms of certain neighborhoods and forbidden submaps. Further restrictions of Fitch maps are considered. Moreover, we show that the least-resolved tree explaining a Fitch map is unique (up to isomorphism). In addition, we provide a polynomial-time algorithm to decide whether $\epsilon$ is a Fitch map and, in the affirmative case, to construct the (up to isomorphism) unique least-resolved tree $(T^{\ast },{\lambda }^{\ast })$ that explains $\epsilon$.