A New Approach for Approximating Directed Rooted Networks

We consider the k-outconnected directed Steiner tree problem (k-DST). Given a directed edge-weighted graph G=(V,E,w), where \(V = \r\ \cup S \cup T\), and an integer k, the goal is to find a minimum cost subgraph of $G$ in which there are k edge-disjoint rt-paths for every terminal \(t \in T\).
The problem is known to be NP-Hard. Furthermore,the question on whether a polynomial time, subpolynomial approximation algorithm exists for k-DST was answered negatively by Grandoni \etal (2018), by proving an approximation hardness of \(\Omega(|T|/\log |T|)\) under NP\(\neq\)ZPP.

Inspired by modern day applications, we focus on developing efficient algorithms for k-DST in graphs where terminals have out-degree 0, and furthermore constitute the vast majority in the graph. We provide the first approximation algorithm for k-DST on such graphs, in which the approximation ratio depends (primarily) on the size of S. We present a randomized algorithm that finds a solution of weight at most \(O(k|S| \log|T|)\) times the optimal weight, and with high probability runs in polynomial time.