A practical greedy approximation for the directed Steiner tree problem

The directed Steiner tree (DST) NP-hard problem asks, considering a directed weighted graph with n nodes and m arcs, a node r called root and a set of k nodes X called terminals, for a minimum cost directed tree rooted at r spanning X. The best known polynomial approximation ratio for DST is a $$O(k^\varepsilon )$$ O ( k ε ) -approximation greedy algorithm. However, a much faster k-approximation, returning the shortest paths from r to X, is generally used in practice. We give two new algorithms : a fast k-approximation called Greedy $$_\text {FLAC}$$ FLAC running in $$O(m \log (n)k + \min (m, nk)nk^2)$$ O ( m log ( n ) k + min ( m , n k ) n k 2 ) and a $$O(\sqrt{k})$$ O ( k ) -approximation called Greedy $$_\text {FLAC}^\triangleright $$ FLAC ▹ running in $$O(nm + n^2 \log (n)k +n^2 k^3)$$ O ( n m + n 2 log ( n ) k + n 2 k 3 ) . We provide computational results to show that, Greedy $$_\text {FLAC}$$ FLAC rivals in practice with the running time of the fast k-approximation and returns solution with smaller cost in practice.