# A PTAS for Planar Group Steiner Tree via Bootstrapping Approximation

### Venue

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, ACM, pp. 570-583

### Publication Year

2016

### Authors

Daniel Marx, Erik Demaine, MohammadHossein Bateni, MohammadTaghi Hajiaghayi

### BibTeX

## Abstract

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.