Algorithmes exacts pour le problème de l’arborescence de Steiner

Algorithmes exacts pour le problème de l’arborescence de Steiner 

Les algorithmes exacts présentés dans ce chapitre ont tous été développés pour le problème de l’arbre de Steiner, mais sont facilement adaptables au problème de l’arborescence de Steiner. Il existe deux catégories d’algorithmes : ceux dont la complexité en temps est Fixed-Parameter Tractable (FPT)  vis-à-vis du nombre de terminaux k et ceux utilisant les propriétés de programmes linéaires associés au problème .

Algorithmes exacts paramétrés par k

Le premier algorithme FPT en k conçu pour les problèmes de Steiner est celui de Dreyfus et Wagner. Cet algorithme a posé les bases d’une série d’algorithmes cherchant à réduire sa complexité en temps et/ou sa complexité en espace. Ces algorithmes reposent tous, comme c’est le cas pour l’algorithme de Dijkstra de calcul d’un plus court chemin entre deux nœuds, sur le fait qu’une solution optimale est composées de sous-solutions optimales.

Algorithme de Dreyfus-Wagner [DW71]. Le premier algorithme FPT en k conçu pour les problèmes de Steiner est celui de Dreyfus et Wagner. Il a été redécrit dans [DYWQ07] et [KS06] pour le problème de couverture de groupes par arbre de Steiner et pour DST. Cet algorithme est une extension de l’algorithme de Dijkstra pour les plus courts chemins. Il s’agit d’un algorithme de programmation dynamique qui, pour tout nœud v et tout sous-ensemble de terminaux X’ ⊂ X, construit l’arborescence de Steiner de poids minimum enracinée en v et couvrant X’ . Lorsque v = r et X’ = X, alors l’algorithme s’arrête et renvoie la solution.

La programmation dynamique est basée sur deux faits, Si, premièrement la racine r d’une solution optimale T∗ n’a qu’un seul fils u alors, nécessairement, le sous-arbre enraciné en u est une solution optimale à l’instance I = (G, u, X, ω). Dans le cas contraire, la racine a au moins deux fils et T∗ peut être décrit comme l’union de deux arborescences T1 et T2 disjointes par les sommets sauf en r. Ainsi, les sous-ensembles X1 et X2 de terminaux couverts respectivement par T1 et T2 forment une partition de X.

Il s’initialise avec les arbres T∗ (x, {x}), de poids 0 et ne contenant que le nœud x, pour tout x, et les insère tous dans une liste L, associés à leur poids. Au début de chaque itération, le premier élément T(u, X1) de L est extrait. Pour tout arc (v, u), T(v, X1) est inséré dans L avec le poids ω(v, u) + ω(T(u, X1)), ou s’il était déjà présent, il remplace l’ancien T(v, X1) s’il a un poids plus faible. De même, pour tout X2 ⊂ X disjoint de X1 tel que T(u, X2) soit dans L ou en ait été extrait, l’arborescence T(u, X1 ∪ X2) est insérée dans L avec le poids ω(T(u, X1)) + ω(T(u, X2)), ou remplace l’ancien T(u, X1 ∪ X2) s’il était déjà présent et s’il a un poids plus faible. La liste L est ensuite retriée, si nécessaire, par ordre de poids. La propriété fondamentale de cet algorithme est que tout arbre T(u, X1) extrait de L a un poids optimal : T(u, X1) = T∗ (u, X1). Quand T(r, X) est extrait de L c’est une solution optimale de I. Cet algorithme a une complexité en temps égale à O(3kn + 2k (k + log(n)n + m)) = O∗ (3k) si la liste L est implémentée sous forme d’un tas de Fibonnacci. Sa complexité spatiale est O(2kn).

Les questions que posent l’existence de cet algorithme sont de savoir s’il est possible :
1. de trouver pour le problème de Steiner un algorithme exact en temps FPT en k mais polynomial en espace ; autrement dit, peut-on construire une solution optimale sans stocker toutes les sous-solutions optimales ;
2. de réduire la complexité en temps en dessous de O∗ (3k); autrement dit, peut-on calculer une solution optimale couvrant X’ sans tester l’union des solutions optimales couvrant les partitions de X’.

Algorithme de Nederlof [Ned09]. Enfin, l’algorithme de Nederlof réussit à réduire la complexité en temps à O∗ (2k) tout en conservant un espace polynomial. L’idée est d’utiliser le principe d’inclusion-exclusion. Par le biais d’une formule de programmation dynamique, on peut ainsi décider, dans le cas où les poids sont unitaires, s’il existe une arborescence de poids inférieur à un entier N fixé, en temps égal à 0∗ (2k) et en espace polynomial. L’auteur de cet algorithme précise que, dans le cas où les poids ne sont pas unitaires, une variante utilisant la transformée de Möbius donne le même résultat.

Cet algorithme possède les mêmes défauts que l’algorithme de Bjorklund et al. : la complexité en temps est exacte et dépend linéairement du poids le plus élevé des arcs de l’instance. On peut ajouter qu’à la différence de tous les autres algorithmes, celui-ci ne construit pas l’arborescence optimale mais ne peut que calculer son poids. En effet, ce poids est la résultante d’une somme dont il n’est pas possible d’extraire de l’information. La valeur d’une solution optimale seule ne suffit pas à construire une solution optimale. Cependant, cet algorithme nous donne la valeur d’une solution optimale de toute instance du problème de Steiner. En utilisant l’algorithme 1, nous somme en mesure de construire une solution optimale. Cet algorithme n’utilise qu’un nombre linéaire de fois l’algorithme de Nederlof et est donc également FPT en k et polynomial en espace.

Il n’existe pas aujourd’hui d’algorithme ayant une complexité en temps meilleure que O∗(2k).

Nous introduirons dans le chapitre 10 un algorithme d’une toute autre nature qui est également FPT en k et utilise un espace polynomial pour construire une solution optimale. Ces algorithmes se basent sur le fait qu’il est possible de construire une solution optimale à partir de sous-solutions optimales. Le temps de calcul est exponentiel car le nombre de ces sous-solutions est exponentiel. Une approximation du problème de Steiner peut donc être construite en ne conservant qu’un nombre polynomial de telles sous-solutions. Meilleure sera la qualité de ces sous-solutions, meilleure sera le rapport d’approximation.

Approximabilité du problème de l’arborescence de Steiner

Résultats préliminaires

Cas des graphes sans circuits

Théorème 2.1.1. Il existe une α-approximation pour DST dans le cas général si et seulement s’il existe une α-approximation pour DST dans le cas d’un graphe sans circuits.

Démonstration. La preuve de la condition nécessaire est triviale. Pour démontrer l’implication inverse, nous allons présenter une réduction isofacteur du cas général vers le cas sans circuits. Toute instance I = (G = (V, A), r, X, ω) de DST peut être réduite en une instance sans circuits Ia, conservant le poids de toutes les solutions réalisables . Cette réduction se procède ainsi :
– générer m copies de chaque nœud et les numéroter de 1 à m ;
– relier tout couple de copies d’un même nœud de numéros successifs par un arc de poids nul ;
– pour tout arc (u, v) dans I, relier la ie copie de u à la (i + 1)e copie du nœud v avec un arc de poids ω(u, v), pour tout i < m ;
– la racine de Ia est la première copie de r ;
– les terminaux de Ia sont les dernières copies des terminaux.

Dans cette instance, les solutions réalisables et optimales de I sont transformables en temps polynomial en solutions de Ia de même poids. Inversement, à partir de toute solution réalisable Ta de Ia, il est possible de construire en temps polynomial une solution réalisable de I de poids plus petit. Pour cela, on sélectionne tous les arcs ayant une copie dans Ta. Si le résultat n’est pas une arborescence, alors on peut détecter ses cycles en temps polynomial et retirer une partie des arcs des cycles pour obtenir une arborescence couvrant tous les terminaux et enracinée en r. Le poids de cette arborescence est plus petit que celui de Ta.

Table des matières

Introduction
I Contexte de l’étude
1 Algorithmes exacts pour le problème de l’arborescence de Steiner
1.1 Algorithmes exacts paramétrés par k
1.2 Algorithmes exacts basés sur la programmation linéaire
2 Approximabilité du problème de l’arborescence de Steiner
2.1 Résultats préliminaires
2.2 Résultats d’approximabilité
2.3 Résultats d’inapproximabilité
2.4 Récapitulatif
3 Problèmes connexes au problème de l’arborescence de Steiner
3.1 Problèmes de Steiner
3.2 Problèmes de couverture par ensembles
II Algorithmes d’approximation pour le problème de Steiner
4 Approximations gloutonnes pour le cas général
4.1 Représentation par une expérience de pensée
4.2 Algorithme naïf implémentant de l’expérience
4.3 Amélioration du rapport d’approximation
4.4 Optimisation de l’algorithme FLAC
4.5 Croissance des variables duales
4.6 Évaluation des performances
4.7 Synthèse des résultats
5 Cas des graphes sans circuits structurés en paliers
5.1 Description des instances étudiées
5.2 Résolution par le problème de couverture par ensembles
5.3 Amélioration du rapport d’approximation
5.4 Extension : couvrir avec deux paliers ou plus
5.5 Adaptation au cas général
5.6 Synthèse des résultats
6 Approximation exponentielle pour le cas général
6.1 Séparation des terminaux
6.2 Approximation exponentielle pour la couverture par ensembles
6.3 Généralisation au problème de Steiner
6.4 Synthèse des résultats
Conclusion
III Problèmes de Steiner à branchements contraints
7 Présentation des problèmes étudiés
7.1 Limitation du nombre de nœuds de branchement
7.2 Limitation du nombre de nœuds diffusants
7.3 Origine des contraintes
8 DST avec un nombre limité de nœuds de branchement
8.1 Cas général
8.2 Restriction aux graphes planaires
8.3 Restriction aux graphes sans circuits
8.4 Synthèse des résultats
9 DST avec un nombre limité de nœuds diffusants
9.1 Propriétés du problème
9.2 Construction d’un algorithme d’approximation pour DST
9.3 Résultat d’inapproximabilité pour DSTLD
9.4 Synthèse des résultats
10 Algorithmes paramétrés basés sur une énumération de patrons
10.1 Algorithme exact FPT en k et d pour DSTLD
10.2 Algorithme exact probabiliste FPT en k et ns pour DSTLB et USTLB
10.3 Algorithme exact XP en k et p pour DSTLB et USTLB
10.4 Synthèse des résultats
Conclusion
Conclusion générale
Bibliographie
Annexes

Lire le rapport complet