Tree Violation Distance under Constraints

We consider numerical taxonomy problems, where we are given an \(n \times n\) distance matrix \(D\) and the goal is to compute the closest tree metric to \(D\). In constrained versions of these problems, the input also contains a distance matrix \(L\), and for every pair \(uv\) the distance in the tree between \(u\) and \(v\) should be at least \(L(uv)\); we say that \(L\) describes lower bound constraints on the tree distances. Farach, Kannan, and Warnow [STOC 1993] suggested that constrained versions of these problems are especially relevant for applications. Surprisingly, one cannot hope for much better, as handling both upper and lower bound constraints simultaneously is intractable.