{"id":"arxiv/2610.16926","url":"https://arxiv.org/abs/2610.16926","tags":["cs.DM","cs.CC","math.CO"],"score":0,"title":"Graph Distortion Distances, Gromov-Hausdorff and the Hardness of Gromov-Wasserstein","domain":"cs.DM","source":"arxiv","authors":["Jens Breitung","Timo Gervens","Julius Pörzgen"],"reviews":0,"subject":"cs.DM","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-12","reactions":{}}