Augmenting Graphs to Meet Edge-Connectivity Requirements

What is the minimum number γ of edges to be added to a given graph G so that in the resulting graph the edge-connectivity between every pair \ u,v \ of its nodes is at least a prescribed value $r( u,v )$? Generalizing earlier results of S. Sridhar and R. Chandrasekaran [Integer Programming and Combinatorial Optimization, R. Kannan and W. Pulleyblank, eds., Proceedings of a conference held at the University of Waterloo, University of Waterloo Press, Waterloo, Ontario, Canada, 1990, pp. 467–484] (when G is the empty graph), of K. P. Eswaran and R. E. Tarjan [SIAM Journal on Computing, 5 (1976), pp. 653–665] (when r ( u,v ) ≡ 2), and of G.-R. Cai and Y.-G. Sun [Networks, 19 (1989 ), pp. 151–172 ] (when r ( u,v ) ≡ k 2, we derive a min-max formula for γ and describe a polynomial time algorithm to compute γ. The directed counterpart of the problem is solved in the same sense for the case when r ( u,v ) ≡ k 1 and is shown to be NP-complete if r ( u,v ) ≡ 1 for u,v ∈ T, and r( u,v ) ≡ 0 otherwise where T is a specified subset of nodes. A fundamental tool in the proof is the splitting theorems of W. Mader [Annals of Discrete Mathematics, 3 (1978), pp. 145–164] and L. Lovász [lecture, Prague, 1974; North–Holland, Amsterdam, 1979]. We also rely extensively on techniques concerning submodular functions. The method makes it possible to solve a degree-constrained version of the problem. The minimum-cost augmentation problem can also be solved in polynomial time provided that the edge-costs arise from node-costs, while the problem for arbitrary edge-costs was known to be NP-complete even for r( u,v ) ≡ 2.