Tree-Embedding is a powerful technique for graph problems that reduces difficult problems on general graphs into amenable tree instances. A notable application of “metric-tree” embedding is in the design of approximation algorithm for the group Steiner tree problem (GST). While the metric-tree embedding has numerous applications, it has a limitation that it is not applicable for survivable network design, in which we require 2 or more edge-disjoint paths, because we would lose connectivity information in the process of obtaining a metric-completion graph.

In this talk, we explore applications of the cut-base tree-embedding in the design of approximation algorithms for survivable network design, namely, the k-edge connected group Steiner tree problem (k-GST). We then generalize our techniques and introduce a problem specific tree embedding for the k-edge-connected directed Steiner tree problem (k-DST) and the classical group Steiner tree problem (GST). As a result, we obtain the first non-trivial approximation algorithms for a special case of k-DST and a general case of 2-DST. We further obtain an O(log^2 n)-approximation algorithm for GST on bounded treewidth graphs, which improves upon the previous best approximation ratio of O(log^3 n) by Garg et al., [SODA’98 & J. Algorithms 00].