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, 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(log 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 Ω(log² n/log log n) even in trees. - We prove that the natural cut-based LP relaxation for DST has an integrality gap of O(log² 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 + log k) approximation of Friggstad and Mousavi [ICALP 2023] when R= ω(log² k).