# Reconstructing a graph from shortest paths information

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?

• 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). – Tony Huynh Dec 20 '16 at 13:41
• 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)$. – monkeymaths Dec 20 '16 at 14:44
• @monkeymaths Yes, another variant is restricting A to contain only distances greater than 2. – Mohammad Al-Turkistany Dec 20 '16 at 15:15

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$.
• 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? – Mohammad Al-Turkistany Dec 20 '16 at 15:19