Décomposition arborescente

Exemple de décomposition arborescente.

Étant donné un graphe G, une décomposition arborescente de G est un arbre dont les nœuds sont des sous-ensembles de sommets du graphe tels que :

• les sous-ensembles couvrent les sommets de G ;
• pour toute arête ${\displaystyle (v,w)}$ dans le graphe G, il existe un nœud de l'arbre qui contient v et w ;
• Pour tout sommet v, les nœuds contenant v forment un sous-arbre.

En général, il existe plusieurs décompositions arborescentes.

Formellement, étant donné un graphe ${\displaystyle G=(V,E)}$, une décomposition arborescente de ${\displaystyle G}$ est un couple ${\displaystyle (X,T)}$, où ${\displaystyle X=\{X_{1},\ldots ,X_{n}\}}$ est une famille de sous-ensembles de sommets de ${\displaystyle V}$, et ${\displaystyle T}$ est un arbre dont les nœuds sont étiquetés par ces sous-ensembles ${\displaystyle X_{i}}$, tels que :

• l'union de tous les ${\displaystyle X_{i}}$ de ${\displaystyle X}$ est égale à ${\displaystyle V}$ ;
• pour toute arête ${\displaystyle (v,w)}$ de ${\displaystyle E}$, il existe un nœud ${\displaystyle X_{i}}$ de l'arbre ${\displaystyle T}$ qui contient v et w ;
• si ${\displaystyle X_{i}}$ et ${\displaystyle X_{j}}$ contiennent un même sommet v, alors tous les nœuds ${\displaystyle X_{z}}$ de ${\displaystyle T}$ sur le chemin entre ${\displaystyle X_{i}}$ et ${\displaystyle X_{j}}$ contiennent v.

Cette dernière condition est équivalente au fait que tous les nœuds ${\displaystyle X_{i}}$ de l'arbre ${\displaystyle T}$ contenant un nœud v de ${\displaystyle G}$ induisent un sous-arbre de ${\displaystyle T}$.

Cette méthode s'applique lorsque l'on cherche à résoudre un problème d'optimisation combinatoire dont le graphe fait partie de la donnée. L'idée est de résoudre le problème initial sur chacun des sous-ensembles de la décomposition, puis de fusionner les résultats dans l'arbre à l'aide de méthodes de programmation dynamique. La méthode ne s'applique que pour des problèmes bien particuliers, la coloration de graphes, par exemple.

Le minimum, parmi toutes les décompositions, de la taille moins un du plus grand sous-ensemble est appelée largeur arborescente (treewidth) du graphe. Cette valeur détermine donc l'intérêt d'utiliser la méthode de décomposition. La largeur d'arbre peut être un bon paramètre pour la complexité paramétrée de certains problèmes.

Lorsque l'arbre n'est constitué que d'un chemin, on parle de décomposition linéaire (path-decomposition) et de largeur (arborescente) linéaire (pathwidth).

• Roncier

• Bruno Courcelle, Décompositions arborescentes (Cours Master) (lire en ligne)

• Portail de l'informatique théorique