Bypassing Surface Embeddings: Approximation Schemes for Network Design in Minor-free Metrics

Since the mid 90s, the study of the complexity of classic network design problems such as the traveling salesman problem (TSP), the Steiner tree problem (ST), or the $k$-MST problem on metric spaces such as low-dimensional Euclidean spaces, doubling metrics, planar or minor-free metrics, has led to major improvements of our understanding of the structure of both these important metric spaces, and the underlying problems. In their celebrated work, Arora and Mitchell gave quasi-polynomial-time approximation schemes (QPTAS) for several network design problems in Euclidean space, that have later been improved to polynomial and (near-)linear in some cases. Arora and Mitchell's QPTAS result has been extended by Talwar [STOC'04] to doubling metrics showing that the Euclidean embedding is not a necessary condition to design approximation schemes for network design problems. In the case of planar metrics, the picture is already less satisfactory: The first approximation schemes for Steiner tree only dates back to [] and nothing better than the general case is known for $k$-MST, an open question that has thus been repeatedly asked. Even when approximation schemes are known for the planar case, generalizing them to the minor-free setting is often a major challenge because most of the topological properties are lost. In this case, one of the most important question of the field is whether we bypass these topological arguments to obtain a general framework for network design problems in minor-free metrics? In this paper, we answer by the affirmative by proposing a framework for network design problems in minor-free metrics. We give the first approximation schemes, with quasi-polynomial running time, for $k$-MST, Steiner tree, Steiner forest, Prize-collecting Steiner tree in minor-free metrics. The result on $k$-MST was not known before even for the planar case, while Steiner tree on minor-free metrics has been one of the major challenge. Here we also obtain approximation schmes for the two non-trivial generalizations Steiner forest and Prize-collecting Steiner tree.

• Algorithms and Theory