The Gromov-Hausdorff distance between ultrametric spaces: its structure and computation

The Gromov-Hausdorff distance (dGH) provides a natural way of quantifying the dissimilarity between two given metric spaces. It is known that computing dGH between two finite metric spaces is NP-hard, even in the case of finite ultrametric spaces which are highly structured metric spaces in the sense that they satisfy the so-called strong triangle inequality. Ultrametric spaces naturally arise in many applications such as hierarchical clustering, phylogenetics, genomics, and even linguistics. By exploiting the special structures of ultrametric spaces, (1) we identify a one parameter family dGH(p)p∈[1,∞] of distances defined in a flavor similar to the Gromov-Hausdorff distance on the collection of finite ultrametric spaces, and in particular dGH(1) =dGH. The extreme case when p=∞, which we also denote by uGH, turns out to be an ultrametric on the collection of ultrametric spaces. Whereas for all p∈[1,∞), dGH(p) yields NP-hard problems, we prove that surprisingly uGH can be computed in polynomial time. The proof is based on a structural theorem for uGH established in this paper; (2) inspired by the structural theorem for uGH, and by carefully leveraging properties of ultrametric spaces, we also establish a structural theorem for dGH when restricted to ultrametric spaces. This structural theorem allows us to identify special families of ultrametric spaces on which dGH is computationally tractable. These families are determined by properties related to the doubling constant of metric space. Based on these families, we devise a fixed-parameter tractable (FPT) algorithm for computing the exact value of dGH between ultrametric spaces. We believe ours is the first such algorithm to be identified.