A PTAS for Planar Group Steiner Tree via Bootstrapping Approximation

We present the first polynomial-time approximation scheme (PTAS), i.e., (1 + ε)-approximation algorithm for any constant ε > 0, for the planar group Steiner tree problem (in which each group lies on a boundary of a face). This result improves on the best previous approximation factor of O(log n(log log n)O(1) ). We achieve this result via a novel and powerful technique called bootstrapping approximation, which allows one to bootstrap from a superconstant approximation factor (even superpolynomial in the input size) all the way down to a PTAS. This is in contrast with the popular ex- isting approach for planar PTASs of constructing light-weight spanners in one iteration, which notably requires a constant-factor approximate solution to start from. Bootstrapping approximation removes the main barrier for designing PTASs for problems which have no known constant-factor approxima- tion (even on planar graphs), and thus can be used to obtain PTASs for several difficult-to-approximate problems. Our second major contribution required for the planar group Steiner tree PTAS is a spanner con- struction, which reduces the graph to have total weight within a factor of the optimal solution while approximately preserving the optimal solution. This is particularly challenging because group Steiner tree requires deciding which terminal in each group to connect by the tree, making it much harder than recent previous approaches to construct spanners for planar TSP by Klein (FOCS’05 & SICOMP’08), subset TSP by Klein (STOC’06), Steiner tree by Borradaile, Klein, and Mathieu (SODA’07 & TALG’09), and Steiner forest by Bateni, Hajiaghayi, and Marx (STOC’10 & JACM’11) (and its improvement to an efficient PTAS by Eisenstat, Klein, and Mathieu (SODA’12)). The spanner construction algorithm first constructs a “pre-spanner” by several steps. we divide the groups in a solution into minimal and non- minimal groups according to whether the optimal solution includes one or multiple vertices of the group. Next we make sure every vertex in a minimal group reached by the optimal solution is in the pre-spanner. By adding more to the pre-spanner, we guarantee that the vertices of (nonminimal) groups reached by the optimal solution but not in the spanner, called tips, exist for only a constant number of nonminimal groups. Next we make sure each such tip of a nonminimal group is first weakly and then via yet another involved step strongly isolated. We are then able to handle strongly isolated tips of one group via another structural result of optimum solutions. Finally we invoke the known spanner construction for Steiner tree as a black box on top of our already constructed pre-spanner to construct an actual spanner. We iterate all the above a polynomial number of times via the bootstrapping approximation technique to obtain the desired PTAS for planar group Steiner tree. Our PTAS for planar group Steiner tree implies the first PTAS for geometric Euclidean group Steiner tree with obstacles, as well as a (2 + ε )-approximation algorithm for group TSP with obstacles, improv- ing over the best previous constant-factor approximation algorithms. By contrast, we show that planar group Steiner forest, a slight generalization of planar group Steiner tree, is APX-hard on planar graphs of treewidth 3, even if the groups are pairwise disjoint and every group is a vertex or an edge.

• Algorithms and Theory