From Directed Steiner Tree to Directed Polymatroid Steiner Tree in Planar Graphs

In the Directed Steiner Tree (DST) problem the input is a directed edge-weighted graph G = (V, E), a root vertex r and a set S ⊆ V of k terminals. The goal is to find a min-cost subgraph that connects r to each of the terminals. DST admits an O(log² k/log log k)-approximation in quasi-polynomial time [29, 27], and an O(k^ϵ)-approximation for any fixed ϵ > 0 in polynomial-time [45, 7]. Resolving the existence of a polynomial-time poly-logarithmic approximation is a major open problem in approximation algorithms. In a recent work, Friggstad and Mousavi [25] obtained a simple and elegant polynomial-time O(log k)-approximation for DST in planar digraphs via Thorup's shortest path separator theorem [41]. We build on their work and obtain several new results on DST and related problems. We develop a tree embedding technique for rooted problems in planar digraphs via an interpretation of the recursion in [25]. Using this we obtain polynomial-time poly-logarithmic approximations for Group Steiner Tree [26], Covering Steiner Tree [34] and the Polymatroid Steiner Tree [5] problems in planar digraphs. All these problems are hard to approximate to within a factor of Ω(log² n/log log n) even in trees [33, 29]. We prove that the natural cut-based LP relaxation for DST has an integrality gap of O(log² k) in planar digraphs. This is in contrast to general graphs where the integrality gap of this LP is known to be Ω(^√k) [46] and Ω(n^δ) for some fixed δ > 0 [36]. We combine the preceding results with density based arguments to obtain poly-logarithmic approximations for the multi-rooted versions of the problems in planar digraphs. For DST our result improves the O(R + log k) approximation of [25] when R = ω(log² k).