A note on Rooted Survivable Networks

The (undirected) Rooted Survivable Network Design (Rooted SND) problem is: given a complete graph on node set V with edge-costs, a root s ∈ V, and (node-)connectivity requirements {r (t) : t ∈ T ⊆ V}, find a minimum cost subgraph G that contains r (t) internally-disjoint st-paths for all t ∈ T. For large values of k = max_{t ∈ T} r (t) Rooted SND is at least as hard to approximate as Directed Steiner Tree [Y. Lando, Z. Nutov, Inapproximability of survivable networks, Theoret. Comput. Sci. 410 (21-23) (2009) 2122-2125]. For Rooted SND, [J. Chuzhoy, S. Khanna, Algorithms for single-source vertex-connectivity, in: FOCS, 2008, pp. 105-114] gave recently an approximation algorithm with ratio O (k² log n). Independently, and using different techniques, we obtained at the same time a simpler primal-dual algorithm with the same ratio.