19
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ 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 $\endgroup$ – Suresh Venkat Nov 28 '11 at 16:28
  • 4
    $\begingroup$ @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. $\endgroup$ – Tsuyoshi Ito Nov 28 '11 at 17:08
  • 2
    $\begingroup$ 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? $\endgroup$ – Artem Kaznatcheev Nov 28 '11 at 18:20
  • 1
    $\begingroup$ 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? $\endgroup$ – Sasho Nikolov Nov 29 '11 at 0:33
  • 3
    $\begingroup$ @SashoNikolov What weights should we assign to the edges? $\endgroup$ – ilyaraz Nov 29 '11 at 6:11
5
$\begingroup$

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:

enter image description here

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.
$\endgroup$
7
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.