Stability of Networks in Stretchable Graphs

In classic optimization theory, the concept of \emph{stability} refers to the study of how much and in which way the optimal solutions of a given minimization problem $\Pi$ can vary as a function of small \emph{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 $\Pi$ is actually a network design problem on a given non-negatively real weighted graph $G=(V,E,w)$ of $n$ nodes and $m$ edges. We focus on a subclass of perturbations, that we name \emph{stretching perturbations}, in which the weights of the edges of $G$ can be increased at most by a fixed multiplying real factor $\lambda \geq 1$. For this class of perturbations, we address the problem of computing the \emph{stability number} of any given subgraph $H$ of $G$ containing at least an optimal solution of $\Pi$, namely the maximum stretching factor for which $H$ keeps on maintaining an optimal solution. Furthermore, given a stretching factor $\lambda$, we study the problem of constructing a \emph{minimal} subgraph of $G$ with stability number greater or equal to $\lambda$. We develop a general technique to solve both problems. By applying this technique to the \emph{minimum spanning tree} and the \emph{single-source shortest paths tree (SPT)} problems, we obtain ${\cal O}(m\alpha(m,n))$ and ${\cal O}(mn(m+n \log n))$ time algorithms, respectively. Furthermore, for the SPT problem, we show that if $H$ coincides with the set of \emph{all} optimal solutions, then the time complexity can be reduced to ${\cal O}(mn)$. Finally, for the \emph{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 the former of our stability problems can be solved in ${\cal O}(mn + n^2 \log n)$ time.