A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
Chandra Chekuri, Rhea Jain · Society for Industrial and Applied Mathematics eBooks · 2025
We consider Directed Steiner Forest (DSF), a fundamental problem in network design. The input to DSF is adirected edge-weighted graph G = (V,E ) and a collection of vertex pairs {(si,ti )}i∈[k]. The goal is to find a minimum cost subgraph H of G such that H contains an si -ti path for each i ∈ [k]. DSF is NP-Hard and is known to be hard to approximate to a factor of Ω(2log1-∈ (n )) for any fixed ∈ > 0 [17]. DSF admits approximation ratios of O (K1/2+∈) [10] and O (n2/3+∈) [4].