<p>I just stumbled across this old question while conducting a lit search, and I happen to have recently gotten answers in <a href="https://arxiv.org/abs/1804.09745" rel="noreferrer">this paper</a> that I might as well share.  I hope the combination of thread necromancy and self-promotion is forgivable.</p>

<blockquote>
  <p>Can we produce any G that would have given these paths as the shortest in polynomial time? The weaker version: can we decide in polynomial time if such G exists?</p>
</blockquote>

<p>The answer is yes to both.  Mohammad's algorithm definitely works, but there's a faster and more direct method that avoids the need to run cubic separation oracles.  Let $H = (V, E, w')$ be an auxiliary undirected weighted graph, where the weight of each edge $e \in E$ is an integer indicating how many of the $n \choose 2$ paths taken on input contain that edge.  Now, consider the edge-capacitated multicommodity flow instance over $H$ (interpreting edge weights as capacities) in which the goal is to simultaneously push 1 unit of flow between each pair of nodes.  Obviously, this MC flow instance can be satisfied by pushing flow in the natural way along the paths given on input.  As it turns out, one can prove that our $n \choose 2$ paths are unique shortest paths in some $G$ if and only if this is the <strong>unique</strong> way to satisfy the MC flow instance.  We can test uniqueness by setting up an LP whose constraints are the usual ones for MC flow feasibility plus a certain carefully chosen objective function, and the edge weights of a satisfying $G$ can be extracted from the dual of this LP.</p>

<blockquote>
  <p>The obvious necessary condition is the following: for every pair of paths their intersection is a path too. Is this condition sufficient?</p>
</blockquote>

<p>This condition is sometimes called "consistency" (a set of paths is consistent if the intersection of any two is a subpath of each).  It follows from the above that consistency is not sufficient.  One of the two tied-for-smallest counterexamples is the following color-coded system of four paths over six nodes:</p>

<p><a href="https://i.sstatic.net/wglXf.png" rel="noreferrer"><img src="https://i.sstatic.net/wglXf.png" alt="enter image description here"></a></p>

<p>In other words, there is no way to assign weights to the 8 edges pictured here so that all of these four paths are simultaneously the unique shortest path between their endpoints.  However, any pair of them intersect on just one node, so they are consistent (even if we fill them out with a few additional paths in the right way to have $n \choose 2$ in total).  There are infinitely many counterexamples like this one; see the paper for a characterization.</p>

<p>Three other quick comments on all this:</p>

<ol>
<li>The analogous statements that you might hope for all hold just fine in the setting of directed rather than undirected graphs,</li>
<li>There is a nice topological interpretation of this theory that leads to some additional insights and intuitions about how unique shortest paths can be structured, and</li>
<li>For some technical reasons, the theory simplifies conveniently in the setting of DAGs rather than undirected or (cyclic) directed graphs.</li>
</ol>

CC BY-SA 4.0
2018-09-20T17:16:24.840Z
2018-09-20T17:16:24.840Z
GMB
<p>You can write the problem as an LP, can't you?  For any two vertices u, v, and any path P from u to v, the weight of P is greater than or equal to the weight of the given shortest path between u and v. These are all linear inequalities, and even though there are exponentially many, the separation problem is in P (it's just an all-pairs shortest path problem).  So, you can use the Ellipsoid algorithm to solve it.</p>

CC BY-SA 3.0
2012-07-27T05:14:11.063Z
2012-07-27T05:14:11.063Z
Mohammad
<p>Suppose we have an undirected weighted graph $G = (V, E, w)$ (with non-negative weights). Let us assume that all shortest paths in $G$ are unique. Suppose we have these $\binom{n}{2}$ paths (sequences of unweighted edges), but do not know $G$ itself. Can we produce any $G$ that would have given these paths as the shortest in polynomial time? The weaker version: can we decide in polynomial time if such $G$ exists?</p>

<p>The obvious necessary condition is the following: for every pair of paths their intersection is a path too. Is this condition sufficient?</p>

CC BY-SA 3.0
2011-11-28T15:06:04.400Z
The set of shortest paths forms a tree, so if G is not a tree you could add all kinds of extra heavy edges and retain the same set of shortest paths
Suresh Venkat
CC BY-SA 3.0
2011-11-28T15:18:55.587Z
The set of *all* shortest paths is not a tree.
ilyaraz
CC BY-SA 3.0
2011-11-28T16:28:13.937Z
I must be confused about the input: if in the union of shortest paths you have two vertices $u,v$ on a cycle, then there are two paths between them (which are shortest necessarily), and one must be shorter than the other by your uniqueness condition
Suresh Venkat
CC BY-SA 3.0
2011-11-28T17:08:57.330Z
@Suresh: I do not know what you want to get at.  If graph G is the complete graph, then the unique shortest path between any two vertices is a single edge, and the union of all these shortest paths is the complete graph.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-28T17:13:45.940Z
argh. never mind. attack of denseness.
Suresh Venkat
CC BY-SA 3.0
2011-11-28T18:20:17.413Z
I think the answer is 'no' for reconstructing a weighted graph, since if any edge is missing from your input, it could actually (a) be missing in the graph or (b) be an edge with a really really high weight. I think the version without weights is more interesting. Also, why is the graph we want to find weighted and the paths we are given unweighted?
Artem Kaznatcheev
CC BY-SA 3.0
2011-11-28T18:21:30.043Z
By reconstruction I didn't mean "unique reconstruction" of course. Could we produce in polynomial time any such $G$?
ilyaraz
CC BY-SA 3.0
2011-11-28T18:42:28.993Z
I would say "restore" or "reconstruct" both imply we want to get the original graph. Perhaps you can edit your question to clarify.
Max
CC BY-SA 3.0
2011-11-29T00:33:01.440Z
let $H$ be the union of the shortest paths. is there a reason why $H$ is not a graph that would produce these same shortest paths? or, in other words, isn't it the case that if the given shortest paths are not shortest paths in $H$, then there is no graph for which they are shortest paths?
Sasho Nikolov
CC BY-SA 3.0
2011-11-29T06:11:16.940Z
@SashoNikolov What weights should we assign to the edges?
ilyaraz
CC BY-SA 3.0
2011-11-29T09:34:40.963Z
ah, weights, i missed that part. ok, that sounds interesting
Sasho Nikolov
<graph-theory><graph-algorithms><co.combinatorics><shortest-path><metrics>
Axioms for Shortest Paths
ilyaraz
# Axioms for Shortest Paths

(Asked by: username_0 on 2011-11-28)

Suppose we have an undirected weighted graph $G = (V, E, w)$ (with non-negative weights). Let us assume that all shortest paths in $G$ are unique. Suppose we have these $\binom{n}{2}$ paths (sequences of unweighted edges), but do not know $G$ itself. Can we produce any $G$ that would have given these paths as the shortest in polynomial time? The weaker version: can we decide in polynomial time if such $G$ exists?

The obvious necessary condition is the following: for every pair of paths their intersection is a path too. Is this condition sufficient?

**Tags:** graph-theory, graph-algorithms, co.combinatorics, shortest-path, metrics

> **Comments:**
> **username_1**: The set of shortest paths forms a tree, so if G is not a tree you could add all kinds of extra heavy edges and retain the same set of shortest paths  
> **username_0**: The set of *all* shortest paths is not a tree.  
> **username_1**: I must be confused about the input: if in the union of shortest paths you have two vertices $u,v$ on a cycle, then there are two paths between them (which are shortest necessarily), and one must be shorter than the other by your uniqueness condition  
> **username_2**: @Suresh: I do not know what you want to get at.  If graph G is the complete graph, then the unique shortest path between any two vertices is a single edge, and the union of all these shortest paths is the complete graph.  
> **username_1**: argh. never mind. attack of denseness.  
> **username_3**: I think the answer is 'no' for reconstructing a weighted graph, since if any edge is missing from your input, it could actually (a) be missing in the graph or (b) be an edge with a really really high weight. I think the version without weights is more interesting. Also, why is the graph we want to find weighted and the paths we are given unweighted?  
> **username_0**: By reconstruction I didn't mean "unique reconstruction" of course. Could we produce in polynomial time any such $G$?  
> **username_4**: I would say "restore" or "reconstruct" both imply we want to get the original graph. Perhaps you can edit your question to clarify.  
> **username_5**: let $H$ be the union of the shortest paths. is there a reason why $H$ is not a graph that would produce these same shortest paths? or, in other words, isn't it the case that if the given shortest paths are not shortest paths in $H$, then there is no graph for which they are shortest paths?  
> **username_0**: @SashoNikolov What weights should we assign to the edges?  
> **username_5**: ah, weights, i missed that part. ok, that sounds interesting  

---

## 2 answers

### Answer by username_6 on 2018-09-20. Score: 5 | Accepted answer

I just stumbled across this old question while conducting a lit search, and I happen to have recently gotten answers in [this paper](https://arxiv.org/abs/1804.09745) that I might as well share. I hope the combination of thread necromancy and self-promotion is forgivable.

> Can we produce any G that would have given these paths as the shortest in polynomial time? The weaker version: can we decide in polynomial time if such G exists?

The answer is yes to both. username_7's algorithm definitely works, but there's a faster and more direct method that avoids the need to run cubic separation oracles. Let $H = (V, E, w')$ be an auxiliary undirected weighted graph, where the weight of each edge $e \in E$ is an integer indicating how many of the $n \choose 2$ paths taken on input contain that edge. Now, consider the edge-capacitated multicommodity flow instance over $H$ (interpreting edge weights as capacities) in which the goal is to simultaneously push 1 unit of flow between each pair of nodes. Obviously, this MC flow instance can be satisfied by pushing flow in the natural way along the paths given on input. As it turns out, one can prove that our $n \choose 2$ paths are unique shortest paths in some $G$ if and only if this is the **unique** way to satisfy the MC flow instance. We can test uniqueness by setting up an LP whose constraints are the usual ones for MC flow feasibility plus a certain carefully chosen objective function, and the edge weights of a satisfying $G$ can be extracted from the dual of this LP.

> The obvious necessary condition is the following: for every pair of paths their intersection is a path too. Is this condition sufficient?

This condition is sometimes called "consistency" (a set of paths is consistent if the intersection of any two is a subpath of each). It follows from the above that consistency is not sufficient. One of the two tied-for-smallest counterexamples is the following color-coded system of four paths over six nodes:

[![enter image description here](https://i.sstatic.net/wglXf.png)](https://i.sstatic.net/wglXf.png)

In other words, there is no way to assign weights to the 8 edges pictured here so that all of these four paths are simultaneously the unique shortest path between their endpoints. However, any pair of them intersect on just one node, so they are consistent (even if we fill them out with a few additional paths in the right way to have $n \choose 2$ in total). There are infinitely many counterexamples like this one; see the paper for a characterization.

Three other quick comments on all this:

1. The analogous statements that you might hope for all hold just fine in the setting of directed rather than undirected graphs,
2. There is a nice topological interpretation of this theory that leads to some additional insights and intuitions about how unique shortest paths can be structured, and
3. For some technical reasons, the theory simplifies conveniently in the setting of DAGs rather than undirected or (cyclic) directed graphs.


---

### Answer by username_7 on 2012-07-27. Score: 7

You can write the problem as an LP, can't you? For any two vertices u, v, and any path P from u to v, the weight of P is greater than or equal to the weight of the given shortest path between u and v. These are all linear inequalities, and even though there are exponentially many, the separation problem is in P (it's just an all-pairs shortest path problem). So, you can use the Ellipsoid algorithm to solve it.


---

