episciences.org_6040_20230325213332354
20230325213332354
episciences.org
raphael.tournoy+crossrefapi@ccsd.cnrs.fr
episciences.org
Discrete Mathematics & Theoretical Computer Science
13658050
06
03
2021
vol. 23 no. 1
Graph Theory
Generalized Fitch Graphs III: Symmetrized Fitch maps and Sets of Symmetric Binary Relations that are explained by Unrooted Edgelabeled Trees
Marc
Hellmuth
Carsten R.
Seemann
https://orcid.org/0000000261305102
Peter F.
Stadler
Binary relations derived from labeled rooted trees play an import role in
mathematical biology as formal models of evolutionary relationships. The
(symmetrized) Fitch relation formalizes xenology as the pairs of genes
separated by at least one horizontal transfer event. As a natural
generalization, we consider symmetrized Fitch maps, that is, symmetric maps
$\varepsilon$ that assign a subset of colors to each pair of vertices in $X$
and that can be explained by a tree $T$ with edges that are labeled with
subsets of colors in the sense that the color $m$ appears in $\varepsilon(x,y)$
if and only if $m$ appears in a label along the unique path between $x$ and $y$
in $T$. We first give an alternative characterization of the monochromatic case
and then give a characterization of symmetrized Fitch maps in terms of
compatibility of a certain set of quartets. We show that recognition of
symmetrized Fitch maps is NPcomplete. In the restricted case where
$\varepsilon(x,y)\leq 1$ the problem becomes polynomial, since such maps
coincide with class of monochromatic Fitch maps whose graphrepresentations
form precisely the class of complete multipartite graphs.
06
03
2021
6040
https://creativecommons.org/licenses/byncsa/4.0
arXiv:2001.05921
10.48550/arXiv.2001.05921
https://arxiv.org/abs/2001.05921v2
https://arxiv.org/abs/2001.05921v1
10.46298/dmtcs.6040
https://dmtcs.episciences.org/6040

https://dmtcs.episciences.org/7493/pdf

https://dmtcs.episciences.org/7493/pdf