Approximating Minimum-Cost Connectivity Problems via Uncrossable Bifamilies

We give approximation algorithms for the Survivable Network problem. The input consists of a graph G = (V, E) with edge/node-costs, a node subset S subset of V, and connectivity requirements {r(s, t) : s, t. T subset of V}. The goal is to find a minimum cost subgraph H of G that for all s, t is an element of T contains r(s, t) pairwise edge-disjoint st-paths such that no two of them have a node in S \ {s, t} in common. Three extensively studied particular cases are: Edge-Connectivity Survivable Network (S = theta), Node-Connectivity Survivable Network (S = V), and Element-Connectivity Survivable Network (r(s, t) = 0 whenever s is an element of S or t is an element of S). Let k = max(s,t is an element of T) r(s, t). In Rooted Survivable Network, there is s is an element of T such that r(u, t) = 0 for all u not equal s, and in the Subset k-Connected Subgraph problem r(s, t) = k for all s, t is an element of T. For edge-costs, our ratios are O(k log k) for Rooted Survivable Network and O(k(2) log k) for Subset k-Connected Subgraph. This improves the previous ratio O(k(2) log n), and for constant values of k settles the approximability of these problems to a constant. For node-costs, our ratios are as follows. -O(k log vertical bar T vertical bar) for Element-Connectivity Survivable Network, matching the best known ratio for Edge-Connectivity Survivable Network. -O(k(2) log vertical bar T vertical bar) for Rooted Survivable Network and O(k(3) log vertical bar T vertical bar) for Subset k-Connected Subgraph, improving the ratio O(k(8) log(2) vertical bar T vertical bar). -O(k(4) log(2) vertical bar T vertical bar) for Survivable Network; this is the first nontrivial approximation algorithm for the node-costs version of the problem.