5
$\begingroup$

Given an undirected and unweighted graph $G = (V, E)$, is it possible to find a mapping $f: V \rightarrow \mathbb{R}^k$ for some $k$ such that for every $i, j \in V$, $\|f(i) - f(j)\|_2^2 = \Delta(i, j)$, where $\Delta(i, j)$ is the shortest path length between $i$ and $j$ in $G$?

I have been testing a few counterexamples for which these isometric embeddings in $\ell_2$ fail to exist (for example, the 4-cycle), but in this case they work.

$\endgroup$
  • $\begingroup$ Notice that the standard metric over the Euclidean space is the $\ell_2$-norm $\|f(i)-f(j)\|_2$, rather than $\|f(i)-f(j)\|_2^2$. Any reason why you consider the squared $\ell_2$-norm? $\endgroup$ – smapers Aug 19 at 14:52
  • $\begingroup$ @smapers Because of the second paragraph? $\endgroup$ – Emil Jeřábek Aug 19 at 14:56
  • $\begingroup$ Oh, ofcourse, thanks! $\endgroup$ – smapers Aug 19 at 14:59
  • 4
    $\begingroup$ Metric embeddings is a well-explored topic. See book by Deza-Laurent springer.com/gp/book/9783540616115 or a web search will reveal several lecture notes and papers on this topic. Square distance embeddings are negative type metrics and one can in fact test, via semi-definite-programming, whether one can embed a given finite metric into a Euclidean space (no restriction on dimension). Many problems here are also NP-Hard. $\endgroup$ – Chandra Chekuri Aug 19 at 19:29
  • $\begingroup$ Thanks Chandra, the pointer turned out to be useful. I'm not an expert of the field and the only relevant theorem I was aware of is due to Schoenberg (ams.org/journals/tran/1938-044-03/S0002-9947-1938-1501980-0/…) but it is quite complicate to work with. $\endgroup$ – Andrea Aug 20 at 14:19
12
$\begingroup$

This is not possible in general.

The 4-cycle is actually helpful to consider: embedding it in $\mathbb{R}^k$ in the way you describe requires the images of all four vertices to be coplanar, forming a square (since the distances between adjacent vertices must be $1$ and those between the non-adjacent pairs must be $\sqrt{2}$).

Now consider the complete bipartite graph $K_{2,3}$. Let us call its vertices $a_1,a_2,b_1,b_2,b_3$. In any embedding $f$ satisfying your condition, the 4-cycles $(a_1,b_1,a_2,b_2)$, $(a_1,b_1,a_2,b_3)$ and $(a_1,b_2,a_2,b_3)$ would all have to be mapped to squares as above, but the first two of these conditions imply $f(b_2) = f(b_3)$, contradiction.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot Klaus. $\endgroup$ – Andrea Aug 20 at 14:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.