Largeur arborescente

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 qui, intuitivement, mesure s'il est proche d'un arbre^[1]. Elle peut être définie de plusieurs manières^{[Lesquelles ?]}, notamment en utilisant la décomposition arborescente.

Souvent, un problème algorithmique facile sur les arbres est en fait facile pour les graphes qui ressemblent à des arbres. Ainsi, ce paramètre est souvent utilisé en algorithmique de graphes, notamment pour les schémas d'approximation polynomiaux et complexité paramétrée. Dans beaucoup d'applications, les graphes ont des largeurs arborescentes petites^{[réf. nécessaire]}, comme par exemple les réseaux sociaux.

Définition

Avec la décomposition arborescente

Exemple d'un graphe G et d'une décomposition arborescente de G.

Définition d'une décomposition arborescente

Informellement, étant donné un graphe non orienté ${\displaystyle G}$, une décomposition arborescente de ${\displaystyle G}$ est un arbre ${\displaystyle T}$ dont les nœuds sont annotés par des sous-ensembles de sommets de ${\displaystyle G}$, qui vérifient les conditions suivantes :

• chaque sommet de ${\displaystyle G}$ apparaît dans l'étiquette d'un nœud de ${\displaystyle T}$ ;
• pour toute arête ${\displaystyle \{v,w\}}$ de ${\displaystyle G}$, il existe un nœud de ${\displaystyle T}$ dont l'étiquette contient ${\displaystyle v}$ et ${\displaystyle w}$ ;
• pour tout sommet ${\displaystyle v}$ de ${\displaystyle G}$, les nœuds de l'arbre qui contiennent ${\displaystyle v}$ forment un sous-arbre connexe de ${\displaystyle T}$.

Formellement, étant donné un graphe non orienté ${\displaystyle G=(V,E)}$, une décomposition arborescente de ${\displaystyle G}$ est un couple ${\displaystyle (T,\lambda )}$ où ${\displaystyle T}$ est un arbre, et ${\displaystyle \lambda }$ est une fonction associant à chaque nœud ${\displaystyle t}$ de ${\displaystyle T}$ un sous-ensemble ${\displaystyle \lambda (t)\subseteq V}$, qui vérifie les conditions suivantes :

• Pour tout sommet ${\displaystyle v\in V}$, il existe un nœud ${\displaystyle t}$ de l'arbre ${\displaystyle T}$ tel que ${\displaystyle v\in \lambda (t)}$. Cette condition revient à imposer que l'union ${\displaystyle \bigcup _{t\in T}\lambda (t)}$ soit égale à ${\displaystyle V}$.
• Pour toute arête ${\displaystyle \{v,w\}\in E}$, il existe un nœud ${\displaystyle t}$ de ${\displaystyle T}$ tel que ${\displaystyle \{v,w\}\subseteq \lambda (t)}$.
• Pour tout sommet ${\displaystyle v\in V}$, les nœuds ${\displaystyle \{t\in T\mid v\in \lambda (t)\}}$ forment un sous-arbre connexe de ${\displaystyle T}$. Cette condition revient à imposer que, pour tous nœuds ${\displaystyle t}$ et ${\displaystyle t'}$ de ${\displaystyle T}$ qui contiennent un même sommet ${\displaystyle v}$ (c'est-à-dire ${\displaystyle v\in \lambda (t)}$ et ${\displaystyle v\in \lambda (t')}$), tous les nœuds ${\displaystyle t''}$ de ${\displaystyle T}$ sur l'unique chaîne simple entre ${\displaystyle t}$ et ${\displaystyle t'}$ satisfont également ${\displaystyle v\in \lambda (t'')}$.

Tout graphe a au moins une décomposition arborescente, par exemple celle où l'arbre ${\displaystyle T}$ a un seul sommet ${\displaystyle t}$ et où ${\displaystyle \lambda (t)=V}$. Dans ce cas, tous les sommets et les arêtes du graphe sont couvertes dans ${\displaystyle \lambda (t)}$, et la condition sur les chemins est trivialement satisfaite. Cependant, cette décomposition n'est pas unique. Plus généralement, tout graphe ${\displaystyle G=(V,E)}$ admet une infinité de décompositions arborescentes : on peut par exemple choisir n'importe quel arbre ${\displaystyle T}$, et définir ${\displaystyle \lambda }$ par ${\displaystyle \lambda (t)=V}$ pour tout nœud ${\displaystyle t}$.

Définition de la largeur arborescente

La largeur arborescente d'une décomposition arborescente ${\displaystyle (T,\lambda )}$ est le cardinal de la plus grande étiquette moins un. Formellement, il s'agit de ${\displaystyle \left(\max _{t\in T}\left|\lambda (t)\right|\right)-1}$. Dans l'exemple de la figure, toutes les étiquettes sont de cardinal 3, donc la largeur arborescente de cette décomposition arborescente est 2. La largeur arborescente (treewidth) d'un graphe G est le minimum de la largeur arborescente parmi toutes les décompositions arborescentes de ce graphe.

Si l'on considère une décomposition arborescente triviale où les nœuds sont étiquetés par l'ensemble ${\displaystyle V}$ de tous les sommets du graphe, on constate que tout graphe avec ${\displaystyle n}$ sommets a une largeur arborescente de ${\displaystyle n-1}$ au plus. En revanche, si ${\displaystyle G}$ est un arbre, si on construit ${\displaystyle T}$ en suivant la structure de ${\displaystyle G}$, on peut obtenir une décomposition arborescente de ${\displaystyle G}$ où chaque étiquette contient exactement deux éléments, donc de largeur 1.

Via les triangulations

Pour tout graphe ${\displaystyle H}$, on note ${\displaystyle \omega (H)}$ l'ordre de la plus grande clique de ${\displaystyle H}$. La largeur arborescente d'un graphe ${\displaystyle G}$ est la plus petite valeur prise par ${\displaystyle \omega (H)-1}$, parmi toutes les triangulations ${\displaystyle H}$ de ${\displaystyle G}$.

Exemples

Les arbres ont largeur d'arbre 1. La clique de taille n a largeur d'arbre n-1. La grille carrée de taille n a une largeur d'arbre égale à n^[2].

Aspects algorithmiques

Calcul de la largeur arborescente

Le calcul de la largeur arborescente est NP-difficile^[3]. Néanmoins, si ${\displaystyle k}$ est fixé, il existe un algorithme linéaire pour déterminer si la largeur arborescente d'un graphe est ${\displaystyle k}$. La dépendance en ${\displaystyle 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, etc.).

Utilisations en algorithmique

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. Si le problème est exprimable en logique monadique du second ordre, le théorème de Courcelle^[4] énonce qu'il peut alors être résolu en temps linéaire (mais la constante est une tour d'exponentielles en ${\displaystyle 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)^[5], 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

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 ${\displaystyle \chi (H)}$ de sa plus grande clique moins un. Deuxièmement, la valeur ${\displaystyle \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 ${\displaystyle \chi (H)}$ qui contient G.

Paramètres de graphes associés

La largeur arborescente peut-être reliée à d'autres paramètres de graphes, comme la dégénérescence ou le roncier.

Une variante pour les graphes orientés a été définie, elle vaut zéro sur les graphes orientés acycliques^[6].

Bibliographie

Ouvrages

• (en) David P. Williamson et David B. Shmoys, Design of approximation algorithms, Cambridge University Press, 2010, 500 p. (présentation en ligne, lire en ligne)
• (en) Hans L. Bodlaender, « A tourist guide through treewidth », Technical report RUU-CS, vol. 92,‎ 1993 (lire en ligne)

Articles

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

Notes et références

1. (en) David P. Williamson et David B. Shmoys, Design of approximation algorithms, Cambridge University Press, 2010, 500 p. (présentation en ligne, lire en ligne), chap. 10.2 (« The maximum independent set problem in planar graphs ») p. 272.
2. Uli Wagner, « Graphs & Algorithms: Advanced Topics Treewidth ».
3. Arnborg, Corneil et Proskurowski 1987.
4. Bruno Courcelle, « The monadic second-order logic of graphs. I. Recognizable sets of finite graphs », Information and Computation, vol. 85, n^o 1,‎ 1^er mars 1990, p. 12–75 (DOI 10.1016/0890-5401(90)90043-H, lire en ligne, consulté le 3 décembre 2017)
5. David P. Williamson et David B. Shmoys, The Design of Approximation Algorithms, 2010, p. 273.
6. Thor Johnson, Neil Robertson, Paul D. Seymour et Robin Thomas, « Directed Tree-Width », J. Comb. Theory, Ser. B, vol. 8, n^o 1,‎ 2001, p. 138-154 (DOI 10.1006/jctb.2000.2031).

Article lié

• Largeur de clique

• Portail des mathématiques
• Portail de l'informatique théorique