Let G=(V,E) be an undirected, unweighted graph with n nodes, m edges and edge connectivity $\lambda$. Given an input parameter $\delta$, the edge augmentation problem is to find the smallest set of edges to add to G so that its edge connectivity is increased by $\delta$. In this paper, we present a solution to this problem which runs in $O(\delta ^2 nm + \delta^3 n^2 + n F(G))$, where F(G) is the time to perform one maximum flow on G. In fact, our solution gives the optimal augmentation for every $\delta '$, $1 \le \delta ' \le \delta$, in the same time bound. By introducing minor modifications to the solution, we can solve the problem without knowing $\delta$ in advance, and we can also solve the node-weighted version and the degree-constrained version of the problem. If $\delta =1$, then our solution is particularly simple; it runs in O(nm) time, and it is a natural generalization of the algorithm in [K. Eswaran and R. E. Tarjan, SIAM J. Comput., 5 (1976), pp. 653--665] for the case where $\lambda+\delta =2$. We also solve the converse problem in the same time bound: given an input number k, increase the connectivity of G as much as possible by adding at most k edges. Our solution makes extensive use of the structure of particular sets of cuts.
['Dalit Naor', 'Dan Gusfield', 'Charles U. Martel']
A Fast Algorithm for Optimally Increasing the Edge Connectivity