Length-Constrained Network Design in Planar Digraphs
arXiv:2607.25811
The paper develops polylogarithmic bicriteria approximation algorithms for length-constrained versions of Directed Steiner Tree and Directed Steiner Forest in planar directed graphs, allowing an O(log k) violation of the length bound.
Abstract
We study length-constrained generalizations of Directed Steiner Tree (DST) and Directed Steiner Forest (DSF) in planar digraphs. In both problems, the input is a directed graph with edge costs. DST asks for a min-cost subgraph connecting a root to a given set of terminals, and DSF asks for a min-cost subgraph connecting each of a given set of source-sink terminal pairs. In the length-constrained setting, each edge has both a cost and a length, and the input includes a length bound ; the goal is to find a min-cost subgraph connecting each terminal pair via a path of length at most . Our work is motivated by a recent line of results showing that several network design problems that are traditionally hard in directed graphs admit polylogarithmic approximation ratios in planar digraphs. We give polylogarithmic bicriteria approximation algorithms for length-constrained analogues of DST and DSF in planar digraphs. Our approximation ratios match the best known for DST and DSF in planar digraphs, with an violation of the length constraint, where denotes the number of terminals (or terminal pairs). As corollaries, we obtain polylogarithmic approximations for buy-at-bulk DST and DSF in planar digraphs.