4
$\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$
3
  • 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, 2016 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$ Dec 20, 2016 at 14:44
  • 1
    $\begingroup$ @monkeymaths Yes, another variant is restricting A to contain only distances greater than 2. $\endgroup$ Dec 20, 2016 at 15:15

1 Answer 1

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$
3
  • 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$ Dec 20, 2016 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, 2016 at 15:35
  • $\begingroup$ I'm not sure this is POLY since this seems to require looping through all possible (connected) graphs on V vertices... $\endgroup$
    – ABIM
    Jun 17, 2023 at 22:01

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.