Marc Hellmuth ; Carsten R. Seemann ; Peter F. Stadler - Generalized Fitch Graphs III: Symmetrized Fitch maps and Sets of Symmetric Binary Relations that are explained by Unrooted Edge-labeled Trees

dmtcs:6040 - Discrete Mathematics & Theoretical Computer Science, June 3, 2021, vol. 23 no. 1 - https://doi.org/10.46298/dmtcs.6040
Generalized Fitch Graphs III: Symmetrized Fitch maps and Sets of Symmetric Binary Relations that are explained by Unrooted Edge-labeled TreesArticle

Authors: Marc Hellmuth ; Carsten R. Seemann ORCID; Peter F. Stadler ORCID

    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 NP-complete. 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 graph-representations form precisely the class of complete multi-partite graphs.


    Volume: vol. 23 no. 1
    Section: Graph Theory
    Published on: June 3, 2021
    Accepted on: May 10, 2021
    Submitted on: January 21, 2020
    Keywords: Computer Science - Discrete Mathematics,Computer Science - Computational Complexity,Computer Science - Data Structures and Algorithms,Mathematics - Combinatorics,68R01, 05C05, 92D15

    1 Document citing this article

    Consultation statistics

    This page has been seen 441 times.
    This article's PDF has been downloaded 190 times.