Multigraph augmentation under biconnectivity and general edge‐connectivity requirements

Given an undirected multigraph G = ( V , E ) and a requirement function r λ : (   V 2 ) → Z + (where (   V 2 ) is the set of all pairs of vertices and Z + is the set of nonnegative integers), we consider the problem of augmenting G by the smallest number of new edges so that the local edge‐connectivity and vertex‐connectivity between every pair x , y ∈ V become at least r λ ( x , y ) and two, respectively. In this paper, we show that the problem can be solved in O ( n 3 ( m + n ) log( n 2 /( m + n ))) time, where n and m are the numbers of vertices and pairs of adjacent vertices in G , respectively. This time complexity can be improved to O (( n m + n 2 log n ) log n ), in the case of the uniform requirement r λ ( x , y )= for all x , y ∈ V . Furthermore, for the general r λ , we show that the augmentation problem that preserves the simplicity of the resulting graph can be solved in polynomial time for any fixed * = max{ r λ ( x , y ) | x , y ∈ V }. © 2001 John Wiley & Sons, Inc.