  We study complexity of rearrangement problems in the generalized breakpoint
model and settle several open questions. The model was introduced by Tannier et
al. (2009) who showed that the median problem is solvable in polynomial time in
the multichromosomal circular and mixed breakpoint models. This is intriguing,
since in most other rearrangement models (DCJ, reversal, unichromosomal or
multilinear breakpoint models), the problem is NP-hard. The complexity of the
small or even the large phylogeny problem under the breakpoint distance
remained an open problem. We improve the algorithm for the median problem and
show that it is equivalent to the problem of finding maximum cardinality
non-bipartite matching (under linear reduction). On the other hand, we prove
that the more general small phylogeny problem is NP-hard. Surprisingly, we show
that it is already NP-hard (or even APX-hard) for 4 species (a quartet
phylogeny). In other words, while finding an ancestor for 3 species is easy,
finding two ancestors for 4 species is already hard. We also show that, in the
unichromosomal and the multilinear breakpoint model, the halving problem is
NP-hard, thus refuting the conjecture of Tannier et al. Interestingly, this is
the first problem which is harder in the breakpoint model than in the DCJ or
reversal models.
