Algorithm for Embedding Graphs with Metric Constraints

Question

Suppose I have a graph $G$ with vertex set $V$, edge set $E \subseteq {V \choose 2}$, and a weight function $w:E \to \mathbb{R}^{+}$. Is there a nice algorithmic way to decide if there is an assignment of vertices to points in Euclidean space, i.e. a function $f: V(G) \to \mathbb{R}^d$ such that $|f(x)-f(y)| = w( \{x,y \})$ whenever $\{ x, , y\} \in E$, where $|.|$ is the Euclidean norm? There is no harm in insisting that the weight function $d$ respect the triangle inequality.

The question I am most interested in is efficiently deciding whether there exists such a function $f$, for a given graph $G$ and weight function $d$, but it might also be interesting to know how to try to find a map that does the job but with "small distortion".
For example, quadratic optimization tells us something…

Cases of special interest: (1) We have a complete graph $G=K_n$, i.e. a finite metric space. (2) The weight function $f$ is constant, i.e. we want to know: is $G$ a unit distance graph in $\mathbb{R}^d$? (Sometimes people want "unit distance graph" to also mean that $f$ is injective, but for my purposes it is fine for vertices to lie on top of each other.) Even the case of $f$ constant and $d=2$ is interesting, as this could be useful for a computational attack on the Hadwiger-Nelson unit coloring problem.

I've noticed that this question is equivalent to asking if a certain real algebraic variety of degree $2$ is nonempty, but I'm not sure if that is a helpful observation, other than it guarantees, for example, that is it algorithmically decidable.

Answer 1

Let's say the graph is complete, and has weights on edges that satisfy triangle inequality. If you want an isometric embedding (which your original question indicates), then there's a necessary and sufficient characterization: the squares of the distances must be of negative type: specifically, given the $D_{ij} = d^2_{ij}$ values, then they must satisfy the inequality

$$ \sum_{i,j} b_i b_j D_{ij} \le 0, \sum_i b_i = 0$$ for all such $b_i$. All of this is discussed rather well in the book by Deza and Laurent.

It gets really interesting when you allow for some distortion. The special case where G is the complete graph and the weights (while not being constant) satisfy the triangle inequality is the well known metric embedding problem, which has been studied extensively in the theoretical computer science community because of connections to multicommodity flows, and also for data mining problems. A great source is the paper by Linial, London and Rabinovich

Let the distortion be the largest value of $w(x,y)/d(x,y)$ (wlog we can assume the embedding always shrinks distances)

1. there's always an embedding into Euclidean space that ensures a distortion $O(\log n)$. The dimension of the space can then be brought down to $O(\log n)$ by applying the Johnson-Lindenstrauss Lemma. This result is due to Bourgain, and the algorithm itself is quite simple: pick $K$ subsets of the input at random, each of size $\log n$, and for each point, let its $i^{th}$ coordinate in the embedding be its distance to the $i^{th}$ such subset. The original proof uses $K = \log^2 n$, and then we use the JL lemma to reduce the dimension back to $\log n$.

1a. this basic construction also works for all $\ell_p$-norms for $1 \le p \le 2$, but the dimensionality reduction of course doesn't.

1b. The construction is tight: the lower bound comes from considering the shortest path metric induced by a constant-degree expander.

The case when you only care to preserve some of the distances is more interesting. While I'm not sure what has been considered for this case, there's another whole body of work that considers the induced shortest path metrics for special graphs (trees, series parallel graphs, planar graphs and so on). One of the most interesting conjectures in this area whether the metric space induced by planar graphs admits a constant-factor distortion embedding into Euclidean space.