The Gromov-Hausdorff distance between ultrametric spaces

Abstract: The Gromov-Hausdorff distance $(d_GH)$ is a natural distance between metric spaces. However, computing $d_GH$ is NP-hard, even in the case of finite ultrametric spaces. We identify a one parameter family $\{d_{GH,p}\}_{p\in[1,\infty]}$ of Gromov-Hausdorff type distances on the collection of ultrametric spaces such that $d_{GH,1}=d_{GH}$. The extreme case when $p=\infty$, which we also denote by $u_{GH}$, turns out to be an ultrametric on the collection of ultrametric spaces. We discuss various geometric and topological properties of $d_{GH,p}$ as well as some of its structural results. These structural results in turn allow us to study the computational aspects of the distance. In particular, we establish that (1) $u_{GH}$ is computationally tractable and (2) when $p < \infty$, although $d_{GH,p}$ is NP-hard to compute, we identify a fixed-parameter tractable algorithm for computing the exact value of $d_{GH,p}$ between finite ultrametric spaces.

algebraic topologydifferential geometrygeneral mathematicsgeneral topologygeometric topologymetric geometry

Audience: researchers in the topic

Topology, Geometry, & Data Analysis (TGDA) Seminar