Le problème de l’arborescence de Steiner (Directed Steiner Tree problem, ou DST, en anglais), consiste, dans un graphe orienté où les arcs sont pondérés, à relier un nœud, appelé racine, à k autres nœuds, appelés terminaux, par une arborescence de coût minimum, éventuellement avec des nœuds intermédiaires. Par exemple, sur le graphe de droite où tous les poids sont égaux à 1, une arborescence de Steiner optmale relie la racine r aux terminaux a, b, c avec 5 arcs. Ce problème s'applique notamment dans la recherche d'arbre de diffusion multicast dans un réseau.
On s'est intéressé ici à la recherche d'algorithmes d'approximations polynomiaux pour ce problème. Le plus petit rapport d’approximation polynomiale connu aujourd’hui pour ce problème est O(kε), pour tout ε > 0. Cependant, en pratique, à cause de son temps de calcul prohibitif, cette approximation est délaissée au profit d’une k-approximation reliant la racine à tous les terminaux avec des plus courts chemins.