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$?
Embed graph in $\ell_2$ space so that edge and non-edge distances are separated by a constant factor
Asked
Viewed
74 times
$\begingroup$
$\endgroup$
-
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
