Suppose I have an undirected unweighted graph $G = (V,E)$. Is there a way to compute points $x_v \in \mathbb{R}^d$ for each vertex $v \in V$ such that $||x_v - x_u|| = 1$ whenever $(u,v) \in E$ and $ ||x_v - x_u|| \geq C$ otherwise, for some constant $C > 1$?

  • 2
    $\begingroup$ Seems that you should be able to write an SDP for this. Search for vector programming and SDP and you will get several pointers. $\endgroup$ – Chandra Chekuri Jul 3 '19 at 11:58
  • $\begingroup$ @ChandraChekuri Thanks! $\endgroup$ – Elliot Gorokhovsky Jul 3 '19 at 11:59
  • $\begingroup$ Note that necessarily $d\geq n-1$, since for the complete graph you have to put all points at distance 1 from eachother. This corresponds to the "n-point uniform metric", mentioned e.g. here. $\endgroup$ – smapers Jul 3 '19 at 12:26

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.