Tree Violation Distance under Constraints

We consider numerical taxonomy problems, where we are given an n×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. Even though there have been multiple breakthroughs in the unconstrained setting, no non-trivial approximation is known in the constrained setting. In this paper, we show that when the objective is to minimize the number of distance disagreements between D and the output tree (Tree Violation Distance), we can achieve a constant factor approximation, even under the presence of lower bound constraints. Regarding techniques, we identify a possible reason for the lack of progress being a particular reduction used in all results in the unconstrained setting, which completely breaks when lower bound constraints are introduced. In particular, we exhibit a simple structure (bad triplet) consisting of only 3 nodes that makes this reduction fail. Interestingly, handling these bad triplets is sufficient: we show that for Tree Violation Distance, one can design a very simple alternative reduction based on repeatedly identifying bad triplets. Additionally, we show that the reduced problem Ultrametric Violation Distance can be solved within a constant-factor approximation, even in the presence of lower bound constraints. At the core of our solution is a remarkably simple LP rounding algorithm that rounds each variable to the closest integer.