Approximating minimum cost connectivity problems via uncrossable bifamilies and spider-cover decompositions

We give approximation algorithms for the Generalized Steiner Network (GSN) problem. The input consists of a graph G = (V, E) with edge/node costs, a node subset S ⊆ V, and connectivity requirements {r(s,t): s,t ∈ T ⊆ V}. The goal is to find a minimum cost subgraph H that for all s, t ∈ T contains r(s,t) pairwise edge-disjoint st-paths so that no two of them have a node in S - {s,t} in common. Three extensively studied particular cases are: Edge-GSN (S = ø), Node-GSN (S = V), and Element-GSN (r(s,t) = 0 whenever s ∈ S or t ∈ S). Let k = max_S,t∈T r(s,t). In Rooted GSN there is s ∈ T so that r(u, t) = 0 for all u ≠ s, and in the Subset k-Connected Subgraph problem r(s, t) = k for all s,t ∈ T. For edge costs, our ratios are O(k²) for Rooted GSN and O(k² logk) for Subset k-Connected Subgraph. This improves the previous ratio O(k² log n) and settles the approximability of these problems to a constant for bounded k. For node-cost, our ratios are: • O(k log|T|) for Element-GSN, matching the best known ratio for Edge-GSN. • O(k² log |T|) for Rooted GSN and O(k³ log |T|) for Subset k-Connected Subgraph, improving the ratio O(k⁸ log² |T|). • O(k ⁴log² |T|) for GSN; this is the first non-trivial approximation algorithm for the problem.