Title: The Gromov-Hausdorff distance between ultrametric spaces
Speaker: Zhengchao Wan (OSU)
Speaker's URL: https://zhengchaow.github.io
Abstract: The Gromov-Hausdorff distance ($d_{\mathrm{GH}}$) is a natural distance between metric spaces. However, computing $d_{\mathrm{GH}}$ is NP-hard, even in the case of finite ultrametric spaces. We identify a one parameter family $\{d_{\mathrm{GH}, p}\}_{p\in[1,\infty]}$ of Gromov-Hausdorff type distances on the collection of ultrametric spaces such that $d_{\mathrm{GH}, 1} =d_{\mathrm{GH}}$. The extreme case when $p=\infty$, which we also denote by $u_{\mathrm{GH}}$, turns out to be an ultrametric on the collection of ultrametric spaces. We discuss various geometric and topological properties of $d_{\mathrm{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_{\mathrm{GH}}$ is computationally tractable and (2) when $p<\infty$, although $d_{\mathrm{GH}, p}$ is NP-hard to compute, we identify a fixed-parameter tractable algorithm for computing the exact value of $d_{\mathrm{GH}, p}$ between finite ultrametric spaces.
