AUGMENTING GRAPHS TO MEET EDGE-CONNECTIVITY REQUIREMENTS

What is the minimum number gamma of edges to be added to a given graph G so that in the resulting graph the edge-connectivity between every pair {u, upsilon} of it nodes is at least a prescribed value r(u, upsilon)? 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, upsilon) = 2), and of G.-R. Cai and Y.-G. Sun [Networks, 19 (1989), pp. 151-172] (when r(u, upsilon) = k greater-than-or-equal-to 2), we derive a min-max formula for gamma and describe a polynomial time algorithm to compute gamma. The directed counterpart of the problem is solved in the same sense for the case when r(u, upsilon) = k greater-than-or-equal-to 1 and is shown to be NP-complete if r(u, upsilon) = 1 for u, upsilon is-an-element-of T, and r(u, upsilon) = 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. Lovasz [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, upsilon) = 2.