The most vital edge on the shortest path

Question

I have this question form the Sedgewick's course on algorithms: "Critical edge. Given an edge-weighted digraph, design an E*log(V) algorithm to find an edge whose removal causes the maximal increase (possibly infinite) in the length of the shortest path from s to t. Assume all of the edge weights are strictly positive. (Hint: compute the shortest path distances d(v) form s to v and consider the reduced costs c′(v,w)=c(v,w)+d(v)−d(w) ≥ 0.)"

I've read on the internet that three (3) guys in 1989 came up with an algorithm of complexity O(E + V*log(V)) what required advanced data structures, and I think it was on a graph (not digraph). If it got three advanced computer scientist to develop this algorithms, is not it too much of a problem for an introductory course? But maybe it is much easier for just O(E*log(V)).

Can you help me to solve it? I don't understand the hint given in the question.

Answer 1

Here is a sketch of an algorithm to find the critical edge on a shortest path, based on Sedgewick's hint.

First, the reduced cost c′(v,w)=c(v,w)+d(v)−d(w) corresponds to the increase in the length of the shortest path from s to w, when going through v just before w. (If v is in the shortest path from s to w then this increase is 0.) (Indeed d(v) is the length of the shortest path from s to v and c(v, w) the cost to go from v to w.)

Suppose the shortest path from s to t is (s, ..., v, t) and that we remove the last edge (v, t). Then the increase in the length of the shortest path from s to t equals the minimum of the c'(u, t) for all in-edges (u, t), with u != v.

Suppose u is such that c'(u, t) is the minimum (still u != v). Then follow the shortest path from s to u backward, until you reach a vertex, say w, belonging to the shortest path from s to t (without any removed edge). The shortest path from s to t is something like (s, ..., w, ..., v, t).

Observe that if you remove any edge between w and t, you will get a maximum increase of c'(u, t) int the shortest path. Indeed, in case one of the edges between w and t is missing, it suffices to go from w to t through the vertex u. On the other hand, note that removing the last edge (v, t) will cause exactly this increase.

Now, just iterate with w what was done with t. Find a vertex x such that c'(x, w) is mininum and x is not on the shortest path. Follow the shortest path from s to x backward until you reach a vertex belonging to the shortest path from s to w.

Once you reach s then you're able to determine which vertex to remove to cause the maximum increase in the lenght of the shortest path.

Answer 2

This is a confusing question, I agree. Here are some my thoughts about it.

The "reduced cost" term and definition is used when reducing the A* search algorithm to Dijkstra's algorithm by replacing the original cost with the reduced cost:

c′(v,w) = c(v,w) - h(v) + h(w) = c(v,w) - (h(v) - h(w)) > 0

The h(v) - h(w) part is a drop of a heuristic function, which should not be more than the edge cost in case of consistent (monotonic) heuristic, thus the reduced cost is still greater than 0 (see slides 14 and 15 here)

It looks like Sedgewick suggests using the original distance function (d(v)) as a consistent heuristic when searching for the new/replacement shortest path in G' which is the same as the original G, but with one removed edge along the original shortest path from s to t. Personally, I don't see how it might help solving the most vital edge problem in O(ElogV) though.

There is also a similar problem: find all downward and upward critical edges in a graph. By definition, decreasing a cost of downward critical edge decreases the overall SP cost. Increasing a cost of upward critical edge increases the overall SP cost. All critical edges can be found in O(ElogV), see ch.8 here. But this does not answer the question what edge is the most critical (causes the max SP increase when removed).

As you noted, the most vital edge problem was solved by Malik, Mittal and Gupta (1989) in O(E + V*log(V)) time. I have not found the original MMG paper, but this presentation explains it quite well. As far as I can see, it can be solved with a priority queue, no specific data structures required.

Sorry for not actually answering the original question (solution for most vital edge in a digraph using reduced costs), but still hoping that the links and thoughts above might be useful for someone. I would be happy to see the solution meant by Sedgewick.