A fast algorithm for optimally increasing the edge connectivity

Abstract

Let G = (V, E) be an undirected, unweighted graph with n nodes, m edges and edge connectivity λ. Given an input parameter δ, the edge augmentation problem is to find the smallest set of edges to add to G so that its edge connectivity is increased by δ. In this paper, we present a solution to this problem which runs in O(δ2nm + δ3n2 + nF(G)), where F(G) is the time to perform one maximum flow on G. In fact, our solution gives the optimal augmentation for every δ′, 1 ≤ δ′ ≤ δ, in the same time bound. By introducing minor modifications to the solution, we can solve the problem without knowing δ in advance, and we can also solve the node-weighted version and the degree-constrained version of the problem. If δ = 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 λ + δ = 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.