Graph Distortion Distances, Gromov-Hausdorff and the Hardness of Gromov-Wasserstein

Jens Breitung, Timo Gervens, Julius Pörzgen

We study the computational complexity of graph distortion distances, a family of graph metrics measuring how vertex distances differ between two graphs. Formally, these distances a…