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 , find a minimum cost subgraph G that contains r(t) internally-disjoint st-paths for all t∈T. For large values of k=maxt∈Tr(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(k2logn). Independently, and using different techniques, we obtained at the same time a simpler primal–dual algorithm with the same ratio.