3
$\begingroup$

Given an undirected unweighted graph $G(V, E)$, there is an efficient algorithm to find the shortest paths between every pair of nodes. I am interested in the reverse problem, we want to reconstruct the original graph given the shortest distances between every pair of nodes.

Reconstruction from shortest paths

INPUT: An integer matrix $A$

Question: Is there a graph $G(V, E)$ such that $A_{(i,j)} $ is the shortest distance between nodes $i$ and $j$.

What is known about the complexity of this problem? Is it solvable by a polynomial-time algorithm? Is it NP-complete?

$\endgroup$
  • 1
    $\begingroup$ Note that $uv$ is an edge of $G$ if and only if the distance between $u$ and $v$ is $1$. Thus, you know all the edges, and hence the entire graph (in polynomial-time). $\endgroup$ – Tony Huynh Dec 20 '16 at 13:41
  • 2
    $\begingroup$ A more interesting question can be obtained if $A$ is not bound to contain distances between ALL pairs of vertices, but just between the vertices in some subset of $V(G)$. $\endgroup$ – monkeymaths Dec 20 '16 at 14:44
  • 1
    $\begingroup$ @monkeymaths Yes, another variant is restricting A to contain only distances greater than 2. $\endgroup$ – Mohammad Al-Turkistany Dec 20 '16 at 15:15
3
$\begingroup$

This problem is solvable in polynomial-time. Given a $V \times V$ distance matrix $A$, let $G$ be the graph with vertex set $V$, where $uw \in E(G)$ if and only if $A_{uw}=1$. Note that $G$ is the only possible graph that has shortest distance matrix $A$. Now just compute all the shortest distances between all pairs of nodes in $G$ (this can be done in polynomial-time by Dijkstra's Algorithm), and check that the distances agree with those in $A$.

$\endgroup$
  • 1
    $\begingroup$ Thanks for your answer. I guess an interesting problem is restricting $A$ to contain only distances greater than 2 . Should I add this variant to the post or should I post a new question? $\endgroup$ – Mohammad Al-Turkistany Dec 20 '16 at 15:19
  • 3
    $\begingroup$ You're welcome. I think the standard protocol is to ask a new question. You can link to this question in the description of the new question if you like $\endgroup$ – Tony Huynh Dec 20 '16 at 15:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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