Gromov-Hausdorff distance and Interleaving distance for Trees

In this talk, I will consider two metrics for (different types of) trees: the Gromov-Hausdorff distance for metric trees and the interleaving distance for the so-called merge trees (used in applications e.g, graphics and visualization). The Gromov-Hausdorff distance is a natural way to measure the distortion between two metric spaces. However, to date, the algorithmic development for computing and approximating Gromov-Hausdorff distance has been limited. In this talk I will focus on computing Gromov-Hausdorff distance for metric trees. Unfortunatley, we show that it is NP hard to approximate it within a factor of 3 even for the case where the underlying trees have unit edge length. On the other hand, interestingly, it turns out that this distance relates to the so-called interleaving distance for merge trees stemmed from the field of computational and applied topology. I will describe this connection, and show how to derive a fixed-parameter-tractable (FPT) algorithm for computing the interleaving distance which in terms gives rise to an approximation algorithm for the Gromov-Hausdorff distance for general metric trees.