Tight Approximation Algorithm for Connectivity Augmentation Problems

The S-connectivity λ S G(u, v) of (u, v) in a graph G is the maximum number of uv-paths that no two of them have an edge or a node in S − {u, v} in common. The corresponding Connectivity Augmentation (CA) problem is: given a graph G0 = (V, E0), 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 λ S G0+F (u, v) ≥ r(u, v) for all u, v ∈ V. Extensively studied particular choices of S 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 rooted {0, 1}-requirements is at least as hard as the Set-Cover problem (in rooted requirements there is s ∈ V − S so that if r(u, v)> 0 then: u = s for directed graphs, and u = s or v = s for undirected graphs). Both directed and undirected node-CA have approximation threshold Ω(2 log1−ε n). The only polylogarithmic approximation ratio known for CA was for rooted requirements – O(log n · log rmax) = O(log 2 n), where rmax = maxu,v∈V r(u, v). No nontrivial approximation algorithms were known for directed CA even for r(u, v) ∈ {0, 1}, nor for undirected CA with S arbitrary. We give an approximation algorithm for the general case that matches the known approximation thresholds. For both directed and undirected CA with arbitrary requirements our approximation ratio is: O(log n) for S = V arbitrary, and O(rmax · log n) for S = V. Key words: