Successive edge-connectivity augmentation problems (Q1300062)

It was shown in \textit{D. Naor}, \textit{D. Gusfield} and \textit{C. Martel} [A fast algorithm for optimally increasing the edge-connectivity, Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, 698-707 (1990); and SIAM J. Comput. 26, No. 4, 1139-1165 (1997; Zbl 0884.05082)] that the so-called successive augmentation property holds for undirected edge-connectivity with uniform demands. That is, for any starting \(G\) which has edge-connectivity \(l\) there exists a sequence \(G= G_0,G_1,G_2,\dots\) of supergraphs of \(G\) such that \(G_{i+1}\) is a supergraph of \(G_i\) and \(G_i\) is an optimal \((l+i)\)-edge-connected augmentation of \(G\) for every \(i\geq 0\). The authors show how to derive this result from a variant of Frank's edge-connectivity algorithm; see \textit{A. Frank} [Augmenting graphs to meet edge-connectivity requirements, SIAM J. Discrete Math. 5, No. 1, 25-53 (1992; Zbl 0782.05054)]. In fact they show that even a stronger version (involving certain non-uniform demands) holds. The authors also show the analogous successive augmentation property holds for directed arc-connectivity augmentations. Finally, they give examples to show that the successive augmentation property does not hold for any of the following possible extensions: hypergraphs, arbitrary non-uniform demands, vertex-connectivity of digraphs.