On tree representations of relations and graphs: symbolic ultrametrics and cograph edge decompositions

Marc Hellmuth () and Nicolas Wieseke ()
Additional contact information
Marc Hellmuth: University of Greifswald
Nicolas Wieseke: Leipzig University

Journal of Combinatorial Optimization, 2018, vol. 36, issue 2, No 15, 616 pages

Abstract: Abstract Tree representations of (sets of) symmetric binary relations, or equivalently edge-colored undirected graphs, are of central interest, e.g. in phylogenomics. In this context symbolic ultrametrics play a crucial role. Symbolic ultrametrics define an edge-colored complete graph that allows to represent the topology of this graph as a vertex-colored tree. Here, we are interested in the structure and the complexity of certain combinatorial problems resulting from considerations based on symbolic ultrametrics, and on algorithms to solve them.This includes, the characterization of symbolic ultrametrics that additionally distinguishes between edges and non-edges of arbitrary edge-colored graphs G and thus, yielding a tree representation of G, by means of so-called cographs. Moreover, we address the problem of finding “closest” symbolic ultrametrics and show the NP-completeness of the three problems: symbolic ultrametric editing, completion and deletion. Finally, as not all graphs are cographs, and hence, do not have a tree representation, we ask, furthermore, what is the minimum number of cotrees needed to represent the topology of an arbitrary non-cograph G. This is equivalent to find an optimal cograph edge k-decomposition $$\{E_1,\dots ,E_k\}$$ { E 1 , ⋯ , E k } of E so that each subgraph $$(V,E_i)$$ ( V , E i ) of G is a cograph. We investigate this problem in full detail, resulting in several new open problems, and NP-hardness results.For all optimization problems proven to be NP-hard we will provide integer linear program formulations to solve them.

Keywords: Symbolic ultrametric; Cograph; Edge partition; Editing; Integer linear program (ILP); NP-complete (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0111-7 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:36:y:2018:i:2:d:10.1007_s10878-017-0111-7

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0111-7

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().