Tight approximation algorithm for connectivity augmentation problems

The S-connectivity λ_G^S(u, v) of (u, v) in a graph G is the maximum number of uv-paths that no two of them have an odgo or a node in S - {u, v} in common. The corresponding Connectivity Augmentation (CA) problem is: given a graph Go = (V, E₀), S ⊆ V, and requirements r(u,v) on V × V, find a minimum size set F of new edges (any edge is allowed) so that λ_G0+F^S(u, v) ≥ r(u, v) for all u, v ε V. Extensively studied particular cases are the edge-CA (when S = Ø) and the node-CA (when S = V). A. Frank gave a polynomial algorithm for undirected edge-CA and observed that the directed case even with r(u, v) ε {0,1} is at least as hard as the Set-Cover problem. Both directed and undirected node-CA have approximation threshold Ω(2^{log1-E n}). We give an approximation algorithm that matches these approximation thresholds. For both directed and undirected CA with arbitrary requirements our approximation ratio is: O(log n) for S ≠ V arbitrary, and O(r_max · log n) for S = V, where r_max = max_u,vεV r(u, v).