  A multilabeled tree (or MUL-tree) is a rooted tree in which every leaf is
labelled by an element from some set, but in which more than one leaf may be
labelled by the same element of that set. In phylogenetics, such trees are used
in biogeographical studies, to study the evolution of gene families, and also
within approaches to construct phylogenetic networks. A multilabelled tree in
which no leaf-labels are repeated is called a phylogenetic tree, and one in
which every label is the same is also known as a tree-shape. In this paper, we
consider the complexity of computing metrics on MUL-trees that are obtained by
extending metrics on phylogenetic trees. In particular, by restricting our
attention to tree shapes, we show that computing the metric extension on
MUL-trees is NP complete for two well-known metrics on phylogenetic trees,
namely, the path-difference and Robinson Foulds distances. We also show that
the extension of the Robinson Foulds distance is fixed parameter tractable with
respect to the distance parameter. The path distance complexity result allows
us to also answer an open problem concerning the complexity of solving the
quadratic assignment problem for two matrices that are a Robinson similarity
and a Robinson dissimilarity, which we show to be NP-complete. We conclude by
considering the maximum agreement subtree (MAST) distance on phylogenetic trees
to MUL-trees. Although its extension to MUL-trees can be computed in polynomial
time, we show that computing its natural generalization to more than two
MUL-trees is NP-complete, although fixed-parameter tractable in the maximum
degree when the number of given trees is bounded.
