Stability of Networks in Stretchable Graphs

In classic optimization theory, the concept of stability refers to the study of how much and in which way the optimal solutions of a given minimization problem Π can vary as a function of small perturbations of the input data. Motivated by congestion problems arising in shortest-path based communication networks, in this paper we restrict ourselves to the case in which Π is actually a network design problem on a given graph G = (V,E,w) of |V| = n nodes, |E| = m edges, and with a positive real weight w(e) on each edge e ∈ E. We focus on a subclass of perturbations, that we call stretching perturbations, in which the weights of the edges of G can be increased by at most a fixed multiplicative real factor λ ≥ 1. For this class of perturbations, we address the problem of computing the stability number of any given subgraph H of G containing at least an optimal solution of Π, namely the maximum stretching factor for which H keeps on maintaining an optimal solution. Furthermore, given a stretching factor λ, we study the problem of constructing a minimal subgraph of G with stability number greater or equal to λ. We develop a general technique to solve both problems. By applying this technique to the minimum spanning tree and the single-source shortest paths tree (SPT) problems, we obtain O(m alpha(m,n)) and O(mn(m+nlogn)) time algorithms, respectively, where alpha(·,·) is the functional inverse of Ackermann’s function. Furthermore, for the SPT problem, we show that if H coincides with the set of all optimal solutions, then the time complexity can be reduced to O(mn) . Finally, for the single-source single-destination shortest path problem, if the optimal solutions of the input instance happen to form a set of vertex-disjoint paths, and H coincides with this set, then we show that we can compute the stability number in O(mn+n^2 logn) time.