Abstract
The nearest neighbor interchange (nni) distance is a classical metric for measuring the distance (dissimilarity) between two evolutionary trees. The problem of computing the nni distance has been studied over two decades (see e.g., [16,3,7,12,8,4]). The long-standing conjecture that the problem is NP-complete was proved only recently, whereas approximation algorithms for the problem have appeared in the literature for a while. Existing approximation algorithms actually perform reasonably well (precisely, the approximation ratios are log n for unweighted trees and 4 log n for weighted trees); yet they are designed for degree-3 trees only. In this paper we present new approximation algorithms that can handle trees with non-uniform degrees. The running time is O(n 2 ) and the approximation ratios are respectively (2d/log d +2) log n and (2d/log d + 12) log n for unweighted and weighted trees, where d ≥ 4 is the maximum degree of the input trees.