title: The complexity of deriving multi-labeled trees from bipartitions.
abstract: Recently, multi-labeled trees have been used to help unravel the evolutionary origins of polyploid species. A multi-labeled tree is the same as a phylogenetic tree except that more than one leaf may be labeled by a single species, so that the leaf set of a multi-labeled tree can be regarded as a multiset. In contrast to phylogenetic trees, which can be efficiently encoded in terms of certain bipartitions of their leaf sets, we show that it is NP-hard to decide whether a collection of bipartitions of a multiset can be represented by a multi-labeled tree. Even so, we also show that it is possible to generalize to multi-labeled trees a well-known condition that characterizes when a collection of bipartitions encodes a phylogenetic tree. Using this generalization, we obtain a fixed-parameter algorithm for the above decision problem in terms of a parameter associated to the given multiset.
authors.affiliation: School of Computing Sciences, University of East Anglia, Norwich, United Kingdom.
authors.forename: Katharina T
authors.initials: KT
authors.lastname: Huber
authors.forename: Martin
authors.initials: M
authors.lastname: Lott
authors.forename: Vincent
authors.initials: V
authors.lastname: Moulton
authors.forename: Andreas
authors.initials: A
authors.lastname: Spillner
mesh_terms: D019143:Evolution, Molecular; D008957:Models, Genetic; D010802:Phylogeny; D011123:Polyploidy