Sensitivity Analysis for Shortest Path Problems and

Sensitivity Analysis for Shortest Path Problems and
Maximum Capacity Path Problems in Undirected Graphs

by Ramkumar Ramaswamy, James B. Orlin, and Nilopal Chakravarti

Abstract. Let G = (N,A) be an undirected graph with n nodes and m arcs, a designated source node s and a sink node t. This paper addresses sensitivity analysis questions concerning the shortest s-t path (SP) problem in G and the maximum capacity s-t path (MCP) problem in G. Suppose that P* is a shortest s-t path in G with respect to a nonnegative distance vector c. For each arc e A, the lower SP tolerance of an arc e is the minimum non-negative value that the length of arc e can take (with all other arc lengths staying fixed) so that P* remains an optimal path. Similarly, the upper SP tolerance of an arc e is the maximum value that the length of arc e can take so that P* remains an optimal path. A special case of this problem is the most vital arc problem.

We show that the problem of finding all tolerances is computationally equivalent to the "Minimum Cost Interval Problem" which we describe as follows. For each i = 1 to m, let [a_i, b_i] denote an interval with endpoints in {1, ..., n}, and an associated cost c_i. For each k = 1 to n, identify a minimum cost interval [a_i, b_i] containing k. Furthermore, we provide an O(m + n log n) algorithm for the Minimum Cost Interval Problem , thus providing an O(m + n log n) algorithm for finding all upper and lower tolerances of arcs in A.

Let Q* be the maximum capacity s-t path in G with respect to capacity vector u. For each arc e A, the lower (resp., upper) MCP tolerance of the arc e is the minimum (resp., maximum) value that the capacity that arc e can take so that Q* remains a maximum capacity path. We show that the problem of finding all upper and lower tolerances of arcs in A can be solved in O(m + n log n)) time. Moreover, the problem of finding all tolerances nearly reduces to the "Minimum Cost Interval Problem."