Farahbakhsh Touli, Elena ;
Wang, Yusu
FPTAlgorithms for Computing GromovHausdorff and Interleaving Distances Between Trees
Abstract
The GromovHausdorff distance is a natural way to measure the distortion between two metric spaces. However, there has been only limited algorithmic development to compute or approximate this distance. We focus on computing the GromovHausdorff distance between two metric trees. Roughly speaking, a metric tree is a metric space that can be realized by the shortest path metric on a tree. Any finite tree with positive edge weight can be viewed as a metric tree where the weight is treated as edge length and the metric is the induced shortest path metric in the tree. Previously, Agarwal et al. showed that even for trees with unit edge length, it is NPhard to approximate the GromovHausdorff distance between them within a factor of 3. In this paper, we present a fixedparameter tractable (FPT) algorithm that can approximate the GromovHausdorff distance between two general metric trees within a multiplicative factor of 14.
Interestingly, the development of our algorithm is made possible by a connection between the GromovHausdorff distance for metric trees and the interleaving distance for the socalled merge trees. The merge trees arise in practice naturally as a simple yet meaningful topological summary (it is a variant of the Reeb graphs and contour trees), and are of independent interest. It turns out that an exact or approximation algorithm for the interleaving distance leads to an approximation algorithm for the GromovHausdorff distance. One of the key contributions of our work is that we redefine the interleaving distance in a way that makes it easier to develop dynamic programming approaches to compute it. We then present a fixedparameter tractable algorithm to compute the interleaving distance between two merge trees exactly, which ultimately leads to an FPTalgorithm to approximate the GromovHausdorff distance between two metric trees. This exact FPTalgorithm to compute the interleaving distance between merge trees is of interest itself, as it is known that it is NPhard to approximate it within a factor of 3, and previously the best known algorithm has an approximation factor of O(sqrt{n}) even for trees with unit edge length.
BibTeX  Entry
@InProceedings{farahbakhshtouli_et_al:LIPIcs:2019:11204,
author = {Elena Farahbakhsh Touli and Yusu Wang},
title = {{FPTAlgorithms for Computing GromovHausdorff and Interleaving Distances Between Trees}},
booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)},
pages = {83:183:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771245},
ISSN = {18688969},
year = {2019},
volume = {144},
editor = {Michael A. Bender and Ola Svensson and Grzegorz Herman},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/11204},
URN = {urn:nbn:de:0030drops112048},
doi = {10.4230/LIPIcs.ESA.2019.83},
annote = {Keywords: GromovHausdorff distance, Interleaving distance, Merge trees}
}
06.09.2019
Keywords: 

GromovHausdorff distance, Interleaving distance, Merge trees 
Seminar: 

27th Annual European Symposium on Algorithms (ESA 2019)

Issue date: 

2019 
Date of publication: 

06.09.2019 