  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 \emph{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, don't 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\}$ of $E$ so that each subgraph
$(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 (ILP) formulations to efficiently solve them.
