- INSTANCE:
A 3-degree (binary) tree
with unique labels on the leaves
and with edge weights
.
A 3-degree tree
*T'*with the same set of unique labels as*T*. - SOLUTION:
A sequence of edges
representing nearest neighbour
interchanges transforming the tree
*T*into*T'*(so that the labels match). A nearest neighbour interchange of is a transformation where one of the two subtrees adjacent to*u*is exchanged with one of the two subtrees adjacent to*v*. - MEASURE:
The cost of the sequence of interchanges, i.e.,
.

*Good News:*Approximable within where*n*is the number of leaves [134].*Comment:*The variation when another type of transformation called*linear-cost subtree transfer*is used is approximable within 2 [134]. MAXIMUM AGREEMENT SUBTREE for three trees of unbounded degree is not approximable within for any , unless NPQP [245].