Edge-connectivity augmentation with partition constraints

In the well-solved edge-connectivity augmentation problem we must find a mi nimum cardinality set F of edges to add to a given undirected graph to make it k-edge-connected. This paper solves the generalization where every edge of F must go between two different sets of a given partition of the vertex set. A special case of this partition-constrained problem, previously unso lved, is increasing the edge-connectivity of a bipartite graph to k while p reserving bipartiteness. Based on this special case we present an applicati on of our results in statics. Our solution to the general partition-constra ined problem gives a min-max formula for \F\ which includes as a special ca se the original min-max formula of Cai and Sun [Networks, 19 (1989), pp. 15 1-172] for the problem without partition constraints. When k is even the min-max formula for the partition-constrained problem is a natural generalization of the unconstrained version. However, this gener alization fails when k is odd. We show that at most one more edge is needed when k is odd and we characterize the graphs that require such an extra ed ge. We give a strongly polynomial algorithm that solves our problem in time O(n (m+n log n) log n). Here n and m denote the number of vertices and distinct edges of the given graph, respectively. This bound is identical to the bes t-known time bound for the problem without partition constraints. Our algor ithm is based on the splitting off technique of Lovasz, like several known efficient algorithms for the unconstrained problem. However, unlike previou s splitting algorithms, when k is odd our algorithm must handle obstacles t hat prevent all edges from being split off. Our algorithm is of interest ev en when specialized to the unconstrained problem, because it produces an as ymptotically optimum number of distinct splits.