3 papers
cs.DM2026
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…
cs.DM2026
The Complexity of Homomorphism Reconstruction Revisited
Timo Gervens, Martin Grohe, Louis Härtel +1
We revisit the algorithmic problem of reconstructing a graph from homomorphism counts that has first been studied in (Böker et al., STACS 2024): given graphs and c…
cs.DM2022
Graph Similarity Based on Matrix Norms
Timo Gervens, Martin Grohe
Quantifying the similarity between two graphs is a fundamental algorithmic problem at the heart of many data analysis tasks for graph-based data. In this paper, we study the comput…