SpeedSteiner: A Fast O ( k 1/2 )-Approximation Algorithm for Directed Steiner Tree
Guangyi Zhang, Nikolaj Tatti, Aristides Gionis · 2025
The directed Steiner tree problem is fundamental in computer science with numerous applications. However, to date, there are no efficient algorithms with quality guarantees. In this paper, we take on this challenge and offer a fast algorithm with provable approximation guarantees. We introduce SpeedSteiner, a O(k1/2)-approximation algorithm, where k is the number of terminal nodes. In practice, SpeedSteiner can be several orders of magnitude faster than other methods with a similar approximation ratio. The speedup is achieved by combining several optimization techniques that exploit the inner structure of recursive-greedy algorithms. We systematically evaluate the proposed algorithm and verify its scalability and strong empirical performance.