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 (² k/ k) -approximation in quasi-polynomial time, and an O (k^) -approximation for any fixed > 0 in polynomial-time. 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 ICALP 2023 obtained a simple and elegant polynomial-time O (k) -approximation for DST in planar digraphs via Thorup's shortest path separator theorem. 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 Friggstad and Mousavi ICALP 2023. Using this we obtain polynomial-time poly-logarithmic approximations for Group Steiner Tree, Covering Steiner Tree, and the Polymatroid Steiner Tree problems in planar digraphs. All these problems are hard to approximate to within a factor of (² n/ n) even in trees. - We prove that the natural cut-based LP relaxation for DST has an integrality gap of O (² k) in planar graphs. This is in contrast to general graphs where the integrality gap of this LP is known to be (k) and (n^) for some fixed > 0. - 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 + k) approximation of Friggstad and Mousavi ICALP 2023 when R= (² k).