Graph Distortion Distances, Gromov-Hausdorff and the Hardness of Gromov-Wasserstein
Abstract
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 are defined in terms of standard matrix norms on the difference of distance matrices under an optimal vertex alignment. The resulting metrics have natural interpretations, corresponding to three ways of measuring the distortion of shortest-path distances: the maximum distortion among all vertex pairs (entrywise maximum norm), global aggregation (entrywise p-norms), and local aggregation (operator p-norms) of distortions. For maximum distortion, we show that approximation below a factor of two is NP-hard even for highly restricted trees. Due to the close connection to the Gromov-Hausdorff distance, we obtain a similar hardness result for the latter. In both cases, we show essentially optimal additive inapproximability. On the algorithmic side, we give a subcubic-time algorithm for optimal embeddings of connected graphs into paths, based on a structural decomposition along a diametral path. Additionally, we give a simple approximation algorithm when one input graph has a "relatively path-like" metric structure, i.e. has bounded pathlength. For local and global distortion, we derive various hardness results even for restricted inputs. Making use of a close connection between the global distortion distances and Gromov-Wasserstein distances, we give the first formal proof of NP-hardness of the latter, which has been claimed in the literature many times but has, to the best of our knowledge, never been correctly proven.
Related
- Gromov-Hausdorff versus Hausdorff distances for Euclidean submanifolds with positive reach
- A Note on the NP-Hardness on Quadratic Optimization over Doubly Stochastic Matrices and the Gromov-Wasserstein Problem
- Gromov-Hausdorff Distances Between Spheres: Asymptotics and Vietoris-Rips Coindex Bounds
- Beyond Procrustes distances: a multilinear Gromov-Wasserstein distance capturing chirality
- Steiner Minimal Trees in the Gromov--Hausdorff Space and in Gromov--Hausdorff Clouds
BibTeX
@misc{breitung2026graph,
title = {{Graph Distortion Distances, Gromov-Hausdorff and the Hardness of Gromov-Wasserstein}},
author = {Jens Breitung and Timo Gervens and Julius Pörzgen},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.16926},
eprint = {2610.16926},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.16926},
}
RIS
TY - UNPB
TI - Graph Distortion Distances, Gromov-Hausdorff and the Hardness of Gromov-Wasserstein
AU - Jens Breitung
AU - Timo Gervens
AU - Julius Pörzgen
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.16926
UR - https://arxiv.org/abs/2610.16926
AB - 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 are defined in terms of standard matrix norms on the difference of distance matrices under an optimal vertex alignment. The resulting metrics have natural interpretations, corresponding to three ways of measuring the distortion of shortest-path distances: the maximum distortion among all vertex pairs (entrywise maximum norm), global aggregation (entrywise p-norms), and local aggregation (operator p-norms) of distortions. For maximum distortion, we show that approximation below a factor of two is NP-hard even for highly restricted trees. Due to the close connection to the Gromov-Hausdorff distance, we obtain a similar hardness result for the latter. In both cases, we show essentially optimal additive inapproximability. On the algorithmic side, we give a subcubic-time algorithm for optimal embeddings of connected graphs into paths, based on a structural decomposition along a diametral path. Additionally, we give a simple approximation algorithm when one input graph has a "relatively path-like" metric structure, i.e. has bounded pathlength. For local and global distortion, we derive various hardness results even for restricted inputs. Making use of a close connection between the global distortion distances and Gromov-Wasserstein distances, we give the first formal proof of NP-hardness of the latter, which has been claimed in the literature many times but has, to the best of our knowledge, never been correctly proven.
ER -