The NP-hardness of the Gromov-Wasserstein distance
<|reference_start|>The NP-hardness of the Gromov-Wasserstein distance: This note addresses the property frequently mentioned in the literature that the Gromov-Wasserstein (GW) distance is NP-hard. We provide the details on the non-convex nature of the GW optimization problem that imply NP-hardness of the GW distance between finite spaces for any instance of an input data. We further illustrate the non-convexity of the problem with several explicit examples.<|reference_end|>
@article{kravtsova2024the,
    title={The NP-hardness of the Gromov-Wasserstein distance},
    author={Natalia Kravtsova},
    journal={arXiv preprint arXiv:2408.06525},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.06525},
    primaryClass={stat.ML cs.LG}
}