7
$\begingroup$

I am interested in the following problem (A) and its related formulation (B). (A) Suppose that $G = (V,E,w)$ is an unknown weighted graph on the vertex set $V$ and that one has access to $d_G(v,v'), \forall v,v'\in V$, where $d_G(\cdot,\cdot)$ is the shortest path metric with respect to $G$. Can one recover the structure (i.e., the edge set $E$ and the weights $w$) of $G$ from just this distance information?

(B) Given a finite metric $(V,d)$, find the sparsest weighted graph $G=(V,E,w)$ that is consistent with $d$ in the sense that $d_G$ is the same as $d$.

I am curious to know if these problems or similar ones have been studied and have interesting answers.

Improve this question
$\endgroup$
1
  • $\begingroup$ I should have added the following statement to (A): More interestingly, is there some non-trivial a priori information that one can give the learner (i.e., the algorithm that is trying to recover the graph) such that this becomes possible? $\endgroup$
    – Skoro
    Commented Jun 30, 2013 at 13:40

2 Answers 2

Reset to default
5
$\begingroup$

Here's a counterexample for (A). Let $V=\{0,1,2\}$, let $E$ consist of $\{0,1\}$ and $\{1,2\}$, each with weight 1. The shortest-path metric would be unchanged if we add a third edge $\{0,2\}$ with weight $2$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Part (B) admits a similarly trivial solution: Start with a complete graph, weighted by the given distances. Then inspect the edges, one after another, and remove any $\{u,v\}$ for which you have edges $\{u,w\}$ and $\{w,v\}$ whose weights add up to the weight of $\{u,v\}$. $\endgroup$
    – Andreas Blass
    Commented Jun 29, 2013 at 15:39
  • $\begingroup$ Thanks for your answer. I guess I am trying to understand if there are interesting restrictions on this problem that have interesting answers. For instance, if we knew a priori that $G$ was a tree, then there is a way to recover $G$ uniquely (compute the minimum spanning tree of the complete weighted graph formed using the pairwise distances). $\endgroup$
    – Skoro
    Commented Jun 29, 2013 at 16:06
2
$\begingroup$

Andreas Blass has produced a simple counterexample to (A) in his answer. I suspect that if your graph is flat in the sense of Andrew Stacey's answer here, then you can in fact recover it from the pairwise distances alone by embedding it a sufficiently high-dimensional Euclidean space.

You can find a nice approximation scheme for question (B) in the paper "Representing graph metrics with fewest edges" by Feder et. al., available here. The basic idea is to add new "Steiner" vertices while removing superfluous edges. The introduction, which is remarkably well-written, contains an overview of how the problem is NP hard, and who did what in which paper, etc. Note that the scheme suggested by Andreas in the comments to his answer does not guarantee that the remaining graph is sparsest possible independent of the order in which the edges are processed.

This is a fairly old problem, and the literature goes back at least to Hakimi and Yau's 1964 paper "The distance matrix of a graph and its realizability". I wasn't able to find a free copy, but you can admire the paywall here.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .