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?

Improve this question
$\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
    Commented 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$
    – monkeymaths
    Commented Dec 20, 2016 at 14:44
  • 1
    $\begingroup$ @monkeymaths Yes, another variant is restricting A to contain only distances greater than 2. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Dec 20, 2016 at 15:15

1 Answer 1

Reset to default
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$.

Improve this answer
$\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$
    – Mohammad Al-Turkistany
    Commented 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
    Commented 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
    Commented Jun 17, 2023 at 22:01

You must log in to answer this question.

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