MINIMUM PHYLOGENETIC TREE DISTANCE

• INSTANCE: A 3-degree (binary) tree $T=\left(V,E\right)$ with unique labels on the leaves and with edge weights $w : E \rightarrow N$. A 3-degree tree T' with the same set of unique labels as T.
• SOLUTION: A sequence of edges $e_1,\ldots,e_m$ representing nearest neighbour interchanges transforming the tree T into T' (so that the labels match). A nearest neighbour interchange of $e_i=\{u,v\}$ 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., $\sum_{1\le i \le m} w(e_i)$.

  
  

• Good News: Approximable within $6+6\log n$ 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 $2^{\log^\delta n}$ for any $\delta<1$, unless NP$\subset$QP [245].