Tight approximation algorithm for connectivity augmentation problems

摘要

The S-connectivity λGS(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 λG0+FS(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 Ω(2log1−εn). The only polylogarithmic approximation ratio known for CA was for rooted requirements—O(logn⋅logrmax)=O(log2n), where rmax=maxu,v∈Vr(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(logn) for S≠V arbitrary, and O(rmax⋅logn) for S=V.