Abstract:

An optimal realization of a given finite metric space is a weighted graph which preserves the metric's distances and has minimal total edge weight. Finding optimal realizations is known to be NP-hard, and solutions are not necessarily unique.

It was conjectured by Andreas Dress in 1984 that any extremally weighted optimal realization could be found as a subgraph of the hereditarily optimal realization $\Gamma_d$, a graph which in general has a higher total edge weight than the optimal realization but has the advantages of being unique, and possible to construct explicitly via the tight span of the metric.

I will present some results and some open questions related to this problem; in particular I will show that there exist counterexamples to Dress's conjecture: graphs such that some, but not all, extremally weighted optimal realizations are subgraphs of $\Gamma_d$.