8
$\begingroup$

Given any undirected edge-weighted graph (with weights > 0) and some dimension d, is there a way to assign positions in $\mathbb{R}^d$ to those vertices such that all of the edges between them have euclidean distance equal to their weights?

The resulting edges may be crossing, that is okay. I'm really interested in the decision problem of when it is or isn't possible but an efficient algorithm to do it when it is possible would also be nice.

$\endgroup$
  • 1
    $\begingroup$ You can find what you're looking for here [convexoptimization.com/TOOLS/cutbook.pdf] in chapter 6. $\endgroup$ – Samuel Schlesinger Mar 22 '17 at 17:49
  • 4
    $\begingroup$ If you fix the dimension d to be less than $n$ the problem is NP-Hard. However, if you only want to know whether there is an embedding into Euclidean space such that the distances are preserved exactly then one can solve this in polynomial time via seme-definite programming. This holds true only for Euclidean distances. $\endgroup$ – Chandra Chekuri Mar 22 '17 at 19:06
  • 1
    $\begingroup$ No efficient algorithm is possible unless $P=NP$. Your problem is hard even for a very restricted case of binary trees (all edges have weight 1). It is NP-complete to decide the existence of an embedding of binary tree in 2D grid such that all edges have unit length. $\endgroup$ – Mohammad Al-Turkistany Mar 24 '17 at 14:16
  • $\begingroup$ What kind of spaces are you interested in? Are you interested in metric spaces? How do you define length in your space? $\endgroup$ – Mohammad Al-Turkistany Mar 25 '17 at 12:03
  • $\begingroup$ @ChandraChekuri You're right! That's cool :) The reduction ends up being pretty trivial but I might write it up as an answer if you don't want to alongside a simple interior point method for completeness. $\endgroup$ – Phylliida Mar 27 '17 at 20:30

Your Answer

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

Browse other questions tagged or ask your own question.