In the Directed Steiner Tree (DST) problem we are given an n-vertex directed edge-weighted graph, a root r , and a collection of k terminal nodes. Our goal is to find a minimum-cost subgraph that contains a directed path from r to every terminal. We present an O(log2 k/loglogk)-approximation algorithm for DST that runs in quasi-polynomial-time. By making standard assumptions, and adjusting the parameters in the hardness result of Halperin and Krauthgamer [STOC’03], we show the matching lower bound of Omega(log^2 k/log log k) for the class of quasi-polynomial-time algorithms. This is the first improvement on the DST problem since the classical quasi-polynomial-time O (log^3 k) approximation algorithm by Charikar et al. [SODA’98 & J. Algorithms’99].

Based on joint work with Fabrizio Grandoni and Bundit Laekhanukit.