A combinatorial arc tolerance analysis for network flow problems

For the separable convex cost flow problem, we consider the problem of determining tolerance set for each arc cost function. For a given optimal flow x, a valid perturbation of cij(x) is a convex function that can be substituted for cij(x) in the total cost function without violating the optimality of x. Tolerance set for an arc(i,j) is the collection of all valid perturbations of cij(x). We characterize the tolerance set for each arc (i,j) in terms of nonsingleton shortest distances between nodes i and j. We also give an efficient algorithm to compute the nonsingleton shortest distances between all pairs of nodes in O(n³) time where n denotes the number of nodes in the given graph.