2015/09/16 by Marc Hellmuth, Hellmuth, Marc, Nicolas Wieseke +1
Business, Management and Accounting · #Business Strategy and Innovation #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1509.05069
openalex publication_date 2015/09/16 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Tree representations of (sets of) symmetric binary relations, or equivalently\nedge-colored undirected graphs, are of central interest, e.g. in\nphylogenomics. In this context symbolic ultrametrics play a crucial role.\nSymbolic ultrametrics define an edge-colored complete graph that allows to\nrepresent the topology of this graph as a vertex-colored tree. Here, we are\ninterested in the structure and the complexity of certain combinatorial\nproblems resulting from considerations based on symbolic ultrametrics, and on\nalgorithms to solve them.\n This includes, the characterization of symbolic ultrametrics that\nadditionally distinguishes between edges and non-edges of \arbitrary\nedge-colored graphs G and thus, yielding a tree representation of G, by\nmeans of so-called cographs. Moreover, we address the problem of finding\n"closest" symbolic ultrametrics and show the NP-completeness of the three\nproblems: symbolic ultrametric editing, completion and deletion. Finally, as\nnot all graphs are cographs, and hence, don't have a tree representation, we\nask, furthermore, what is the minimum number of cotrees needed to represent the\ntopology of an arbitrary non-cograph G. This is equivalent to find an optimal\ncograph edge k-decomposition E1,\…,Ek of E so that each subgraph\n(V,Ei) of G is a cograph. We investigate this problem in full detail,\nresulting in several new open problems, and NP-hardness results.\n For all optimization problems proven to be NP-hard we will provide integer\nlinear program (ILP) formulations to efficiently solve them.\n