Augmenting Graphs to Meet Edge-Connectivity Requirements

Source abstract

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,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 ) \equiv 2$), and of G.-R. Cai and Y.-G. Sun [Networks, 19 (1989 ), pp. 151–172 ] (when $r ( u,v ) \equiv k\geqq 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,v ) \equiv k\geqq 1$ and is shown to be NP-complete if $r ( u,v ) \equiv 1$ for $u,v \in T$, and $r( u,v ) \equiv 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 ) \equiv 2$.