Largeur arborescente

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En théorie des graphes et en informatique théorique, la largeur arborescente ou largeur d'arbre d'un graphe (treewidth en anglais) est un nombre associé au graphe. Ce paramètre mesure, d'une certaine façon, à quel point un graphe est proche d'un arbre. Ce nombre peut être défini de plusieurs manière, notamment en utilisant la décomposition arborescente.

Ce paramètres est souvent utilisé en algorithmique de graphes, notamment pour les schémas d'approximation polynomiaux.

Définition[modifier | modifier le code]

Avec la décomposition arborescente[modifier | modifier le code]

Exemple de décomposition arborescente.

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

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

Cette dernière condition est équivalente au fait que tous les nœuds X_i de l'arbre T contenant un nœud v de G induisent un sous-arbre de T.

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

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.

Interprétation[modifier | modifier le code]

La largeur d'arbre est une façon de savoir si un graphe est proche d'un arbre[1].

Familles de graphes de largeur arborescente bornée[modifier | modifier le code]

Aspects algorithmiques[modifier | modifier le code]

Calcul de la largeur arborescente[modifier | modifier le code]

Le calcul de la largeur arborescente est NP-difficile[2]. Néanmoins, si k est fixé, il existe un algorithme linéaire pour déterminer si la largeur arborescente d'un graphe est k. La dépendance en k du temps d'exécution de l'algorithme est cependant exponentielle. Pour certaines classes particulières de graphes, calculer la largeur arborescente se fait en temps polynomial (arbres, graphes triangulés,… ).

Utilisations en algorithmique[modifier | modifier le code]

De nombreux problèmes de graphes NP-difficiles dans le cas général peuvent être résolus en temps polynomial si on se restreint aux graphes de largeur arborescente bornée. C'est donc un bon paramètre pour la complexité paramétrée. Il existe même un théorème général : si le problème est exprimable en logique monadique du second d'ordre, il peut même être résolu en temps linéaire (mais la constante est une tour d'exponentielles en k qui rend l'algorithme inapplicable en général).

Par exemple le problème du stable maximum pour des graphes planaires, peut-être résolu en temps polynomial pour une largeur arborescente bornée (on prend alors cette largeur comme une constante)[3], ce qui permet d'obtenir un schéma d'approximation en temps polynomial quand on ne contraint pas la largeur.

Liens avec les graphes triangulés[modifier | modifier le code]

Le concept de décomposition arborescente a un lien très fort avec les graphes triangulés. Premièrement, la largeur arborescente d'un graphe triangulé H est égale à la taille \chi(H) de sa plus grande clique moins un. Deuxièmement, la valeur \chi(H) peut être calculée à l'aide d'un algorithme linéaire si le graphe H est triangulé. Dans la littérature de recherche opérationnelle, les algorithmes de calcul de la largeur arborescente d'un graphe G cherchent souvent à déterminer le graphe triangulé H de plus petite valeur \chi(H) qui contient G.

Paramètres de graphes associés[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

Ouvrages[modifier | modifier le code]

Articles[modifier | modifier le code]

  • S. Arnborg, D. Corneil et A. Proskurowski, « Complexity of finding embeddings in a k-tree », SIAM Journal on Matrix Analysis and Applications, vol. 8, no 2,‎ 1987, p. 277–284 (lien DOI?)

Notes et références[modifier | modifier le code]

  1. (en) David P. Williamson et David B. Shmoys, Design of approximation algorithms, Cambridge University Press,‎ 2010, 500 p. (résumé, lire en ligne), chap. 10.2 (« The maximum independent set problem in planar graphs ») p. 272
  2. (Arnborg, Corneil et Proskurowski 1987)
  3. Williamson et David B. Shmoys, The design of approximation algorithms,‎ 2010 p. 273