Characterizing Cell-Decomposable Metrics

Abstract

To a finite metric space $(X,d)$ one can associate the so called tight-span $T(d)$ of $d$, that is, a canonical metric space $(T(d),d_\infty)$ into which $(X,d)$ isometrically embeds and which may be thought of as the abstract convex hull of $(X,d)$. Amongst other applications, the tight-span of a finite metric space has been used to decompose and classify finite metrics, to solve instances of the server and multicommodity flow problems, and to perform evolutionary analyses of molecular data. To better understand the structure of $(T(d),d_\infty)$ the concept of a cell-decomposable metric was recently introduced, a metric whose associated tight-span can be decomposed into simpler tight-spans. Here we show that cell-decomposable metrics and totally split-decomposable metrics — a class of metrics commonly applied within phylogenetic analysis — are one and the same thing, and also provide some additional characterizations of such metrics.