Set connectivity problems in undirected graphs and the directed Steiner network problem

In the generalized connectivity problem, we are given an edge-weighted graph G = (V,E) and a collection D = {(S1, T1),..., (Sk, Tk)} of distinct demands; each demand (Si, Ti) is a pair of disjoint vertex subsets. We say that a subgraph F ⊆ G connects a demand (Si, Ti) when it contains a path with one endpoint in Si and the other in Ti. The goal is to identify a minimum weight subgraph that connects all demands in D. Alon et al. (SODA ’04) introduced this problem to study online network formation settings and showed that it captures some well-studied problems such as Steiner forest, non-metric facility location, tree multicast, and group Steiner tree. Finding a non-trivial approximation ratio for generalized connectivity was left as an ope