A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs

We consider Directed Steiner Forest (DSF), a fundamental problem in network design. The input to DSF is a directed edge-weighted graph G = (V, E) and a collection of vertex pairs (s i , t i ) i∈ [k] . The goal is to find a minimum cost subgraph H of G such that H contains an s i -t i path for each i ∈ [k]. DSF is NP-Hard and is known to be hard to approximate to a factor of Ω(2 log 1-ǫ (n) ) for any fixed ǫ > 0 [17]. DSF admits approximation ratios of O(k 1/2+ǫ ) [10] and O(n 2/3+ǫ ) [4].

In this work we show that in planar digraphs, an important and useful class of graphs in both theory and practice, DSF is much more tractable. We obtain an O(log 6 k)-approximation algorithm via the junction tree technique. Our main technical contribution is to prove the existence of a low density junction tree in planar digraphs. To find an approximate junction tree we rely on recent results on rooted directed network design problems [24,11], in particular, on an LP-based algorithm for the Directed Steiner Tree problem [11]. Our work and several other recent ones on algorithms for planar digraphs [24,36,11] are built upon structural insights on planar graph reachability and shortest path separators [41].