Axioms for Shortest Paths

Question

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?

Answer 1

I just stumbled across this old question while conducting a lit search, and I happen to have recently gotten answers in this paper 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. 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 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:

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 2

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.