Efficient online sensitivity analysis for the injective bottleneck path problem

The tolerance of an element of a combinatorial optimization problem with respect to a given optimal solution is the maximum change, i.e., decrease or increase, of its cost, such that this solution remains optimal. The bottleneck path problem, for given an edge-capacitated graph, a source, and a target, is to find the \(\max \) $max$ - \(\min \) $min$ value of edge capacities on paths between the source and the target. For any given sample of this problem with n vertices and m edges, there is known the Ramaswamy-Orlin-Chakravarty’s algorithm to compute an optimal path and all tolerances with respect to it in \(O(m+n\log n)\) $O(m+nlogn)$ time. In this note, for any in advance given (n, m)-network with distinct edge capacities and k source-target pairs, we propose an \(O\Big (m \alpha (m,n)+\min \big ((n+k)\log n,km\big )\Big )\) $O(m\alpha (m,n)+min((n+k)logn,km))$ -time preprocessing, where \(\alpha (\cdot ,\cdot )\) $\alpha (·,·)$ is the inverse Ackermann function, to find in O(k) time all 2k tolerances of an arbitrary edge with respect to some \(\max \min \) $maxmin$ paths between the paired sources and targets. To find both tolerances of all edges with respect to those optimal paths, it asymptotically improves, for some n, m, k, the Ramaswamy-Orlin-Chakravarty’s complexity \(O\big (k(m+n\log n)\big )\) $O(k(m+nlogn))$ up to \(O(m\alpha (n,m)+km)\) $O(m\alpha (n,m)+km)$ .