Problème de l'arbre de Steiner

Dans un espace métrique, étant donné un ensemble de points P, un arbre pour P est un réseau (c'est-à-dire un ensemble de chemins connectés) tel que tous les points soient reliés, et un arbre est dit de Steiner si la longueur totale du réseau est minimale[1].

Dans la variante euclidienne du problème, l'espace métrique est un espace euclidien.

Le cadre le plus classique en optimisation combinatoire est le suivant : étant donné un graphe G, dont les arêtes ont des poids, et un sous-ensemble S de sommets de G, trouver un ensemble d'arêtes de poids minimal tel que le sous-graphe induit soit connexe et contienne tous les sommets de S[2].

Dans les deux problèmes, étant donné un ensemble V de sommets, il s'agit de trouver un arbre A de coût minimal reliant tous les sommets de V (où le coût de l'arbre est défini comme la somme du coût de ses arêtes). Contrairement au problème de l'arbre couvrant minimal où tous les sommets de l'arbre A doivent être dans V, dans le problème de l'arbre de Steiner il est autorisé d'utiliser des points en dehors de V.

Il existe différentes contraintes que l'on peut appliquer à l'arbre. La plupart des problèmes sont NP-complets (donc considérés comme difficiles à calculer). Quelques cas de figures sont solubles en temps polynomial. Il existe des algorithmes d'approximation pour le problème[2], par exemple une (2-2/|S|)-approximation peut être obtenue en calculant un «arbre couvrant à terminaux de coût minimum» (minimum cost terminal spanning tree), c'est-à-dire un arbre couvrant dans un graphe adapté.

Un des algorithmes les plus connus est celui fournit par Melzack[3] en 1961 consistant à partir du problème à trois sommets posé par Fermat résolu par le mathématicien Italien Evengelista Torricelli. Il s'agit de réduire le nombre de points pour revenir à ce problème et ensuite faire revenir les points au fur et à mesure. Avant Melzack il n’existait aucun moyen de résoudre un problème à plus de 20 points. A ce jour l'algorithme exact le plus efficace semble être GeoSteiner[4].

• (en) Viggo Kahn, « Minimum Steiner Tree », sur A compendium of NP optimization problems, mars 2000
• (en) Ronald L Graham: The Shortest Network Problem, film de 1988
• (en) « Steiner tree problem », dans Michiel Hazewinkel, Encyclopædia of Mathematics, Springer, 2002 (ISBN 978-1556080104, lire en ligne)

• (en) F.K. Hwang, D.S. Richards, P. Winter, The Steiner Tree Problem, Elsevier, North-Holland, 1992, (ISBN 0-444-89098-X) (Annals of Discrete Mathematics, vol. 53).