10
$\begingroup$

Suppose I have a graph $G$ with vertex set $V$, edge set $E \subseteq {V \choose 2}$, a poistive integer $d$, 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 respects 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$, dimension $d$, and weight function $w$, 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 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.

$\endgroup$
1
  • $\begingroup$ Do you have to insist on the Euclidean norm? The injective "max" norm is much more attractive from the general point of view of metric spaces. $\endgroup$
    – Wlod AA
    Feb 13, 2023 at 3:53

2 Answers 2

12
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Correct me if I am wrong : Doesn't section 2.6 of the paper "Local-Global Tradeoffs in Metric Embedding" by Moses-Yury-Konstantin supersede Linial-London-Rabinovich? (It would be great if you could compare the two papers and what is the most recent thing known in this direction!) $\endgroup$
    – Student
    Aug 26, 2015 at 1:17
  • $\begingroup$ What is the name of the paper by Linial, London and Rabinovich? I think that the link is broken now? Thank you! $\endgroup$
    – real
    Nov 18, 2015 at 15:46
  • $\begingroup$ Found it. It must be the "The geometry of graphs and some of its algorithmic applications". $\endgroup$
    – real
    Nov 18, 2015 at 16:04
0
$\begingroup$

One may always be able to find a graph embedding in Euclidean space, if we consider dot product instead of euclidean norm.

If the distance matrix $D_G$ is a diagonalizable matrix, than we can perform eigenvalue decomposition as $D_G=U\Sigma U^T = U\Sigma^{1/2} \Sigma^{1/2}U^{T}=K^{T}K$. Now, each row $K$ can be treated as a euclidean representation of graph vertex whose dot product with other any row yield the corresponding weight of an edge.

$\endgroup$
1
  • 1
    $\begingroup$ This only works if the eigenvalues are real and non-negative, at which point you might as well use the Choleksy decomposition. $\endgroup$
    – henrikl
    May 19, 2021 at 6:55

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.