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.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ You can find what you're looking for here [convexoptimization.com/TOOLS/cutbook.pdf] in chapter 6. $\endgroup$
    – Samuel Schlesinger
    Mar 22, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 20:30

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.