The NP-hardness of the Gromov-Wasserstein distance

Code

• github.com/kravtsova2/GW_NPhard
  Officialnone★ 1

Abstract

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.

Reproductions