The Gromov-Hausdorff distance between ultrametric spaces: its structure and computation
share
The Gromov-Hausdorff distance (d_GH) provides a natural way of quantifying the dissimilarity between two given metric spaces. It is known that computing d_GH 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 {d_GH^(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 d_GH^(1) =d_GH. The extreme case when p=∞, which we also denote by u_GH, turns out to be an ultrametric on the collection of ultrametric spaces. Whereas for all p∈[1,∞), d_GH^(p) yields NP-hard problems, we prove that surprisingly u_GH can be computed in polynomial time. The proof is based on a structural theorem for u_GH established in this paper; (2) inspired by the structural theorem for u_GH, and by carefully leveraging properties of ultrametric spaces, we also establish a structural theorem for d_GH when restricted to ultrametric spaces. This structural theorem allows us to identify special families of ultrametric spaces on which d_GH 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 d_GH between ultrametric spaces. We believe ours is the first such algorithm to be identified.
READ FULL TEXT