A Note on the NP-Hardness on Quadratic Optimization over Doubly Stochastic Matrices and the Gromov-Wasserstein Problem
Abstract
The Gromov-Wasserstein problem is an extension of the regular optimal transport problem that is adapted for pairs of distributions residing in incomparable spaces. Broadly speaking, given a pair of metric measure spaces, the Gromov-Wasserstein problem seeks couplings between these spaces that minimize the distortion between the metric evaluations. In this note we record the fact that the Gromov-Wasserstein distance between finite metric spaces is NP-Hard to compute. Our argument relies on a reduction from the Hamiltonian Cycle Problem, and it builds on ideas in Vayer's thesis and Ryner et. al's work that draw connections between the 2-Gromov-Wasserstein and the Quadratic Assignment Problem. During the preparation of this manuscript we learned of the appearance of Breitung et. al's work, whose result essentially supersedes ours. We hope this note serves as a useful companion whose proof is, hopefully, more elementary and easier to understand.
Related
- Distributionally robust chance-constrained standard quadratic optimization with Wasserstein ambiguity
- Noise-Robust Distributed Optimization Over Directed Graphs With Row Stochastic Matrices
- Graph Distortion Distances, Gromov-Hausdorff and the Hardness of Gromov-Wasserstein
- Dissipation Bounds and Hardness in Globally Asymptotically Stable Quadratic Systems
- The p-Bures-Wasserstein distance via 3×3 block matrices (with application to p-Bures-Wasserstein barycenters)
BibTeX
@misc{soh2026note,
title = {{A Note on the NP-Hardness on Quadratic Optimization over Doubly Stochastic Matrices and the Gromov-Wasserstein Problem}},
author = {Yong Sheng Soh},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.00479},
eprint = {2611.00479},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.00479},
}
RIS
TY - UNPB
TI - A Note on the NP-Hardness on Quadratic Optimization over Doubly Stochastic Matrices and the Gromov-Wasserstein Problem
AU - Yong Sheng Soh
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.00479
UR - https://arxiv.org/abs/2611.00479
AB - The Gromov-Wasserstein problem is an extension of the regular optimal transport problem that is adapted for pairs of distributions residing in incomparable spaces. Broadly speaking, given a pair of metric measure spaces, the Gromov-Wasserstein problem seeks couplings between these spaces that minimize the distortion between the metric evaluations. In this note we record the fact that the Gromov-Wasserstein distance between finite metric spaces is NP-Hard to compute. Our argument relies on a reduction from the Hamiltonian Cycle Problem, and it builds on ideas in Vayer's thesis and Ryner et. al's work that draw connections between the 2-Gromov-Wasserstein and the Quadratic Assignment Problem. During the preparation of this manuscript we learned of the appearance of Breitung et. al's work, whose result essentially supersedes ours. We hope this note serves as a useful companion whose proof is, hopefully, more elementary and easier to understand.
ER -