Optimal realizations of two-dimensional, totally-decomposable metrics

A realization of a metric dd on a finite set XX is a weighted graph (G,w)(G,w) whose vertex set contains XX such that the shortest-path distance between elements of XX considered as vertices in GG is equal to dd. Such a realization (G,w)(G,w) is called optimal if the sum of its edge weights is minimal over all such realizations. Optimal realizations always exist, although it is NP-hard to compute them in general, and they have applications in areas such as phylogenetics, electrical networks and internet tomography. A. Dress (1984) showed that the optimal realizations of a metric dd are closely related to a certain polytopal complex that can be canonically associated to dd called its tight-span. Moreover, he conjectured that the (weighted) graph consisting of the zero- and one-dimensional faces of the tight-span of dd must always contain an optimal realization as a homeomorphic subgraph. In this paper, we prove that this conjecture does indeed hold for a certain class of metrics, namely the class of totally-decomposable metrics whose tight-span has dimension two. As a corollary, it follows that the minimum Manhattan network problem is a special case of finding optimal realizations of two-dimensional totally-decomposable metrics.