Roncier (théorie des graphes)

Un roncier d'ordre 4 dans le graphe en grille 3 x 3, composé de six sous-graphes connexes reliés deux-à-deux.

En théorie des graphes, un roncier (ou une ronce) pour un graphe non orienté G est une famille de sous-graphes connexes de G qui sont reliés deux-à-deux : pour chaque paire de sous-graphes disjoints, il existe une arête de G qui a une extrémité dans chacun de ces sous-graphes. LModèle:'ordre d'un roncier est la plus petite taille d'une couverture, c'est-à-dire d'un ensemble de sommets de G qui a une intersection non vide avec chacun des sous-graphes. Les ronciers peuvent être utilisés pour caractériser la largeur arborescente de G.

Largeur d'arbre et refuge

Un refuge d'ordre k dans un graphe G est une fonction $\beta$ qui associe, à chaque ensemble X de moins de k sommets, une composante connexe de $G-X$ de telle sorte que deux sous-ensembles $\beta (X)$ et $\beta (Y)$ quelconques ont une arête qui les relie. Ainsi, l'ensemble des images de $\beta$ forme un roncier dans G d'ordre k. Réciproquement, chaque roncier peut être utilisé pour déterminer un refuge : pour chaque ensemble X de taille inférieure à l'ordre du roncier, il existe une composante connexe unique $\beta (X)$ qui contient tous les sous-graphes du roncier qui sont disjoints de X.

Comme l'ont montré Seymour et Thomas, l'ordre d'un roncier (ou de manière équivalente d'un refuge) caractérise la largeur arborescente : un graphe a un roncier d'ordre k si et seulement s'il a une largeur d'arbre supérieure ou égale à k-1.

Taille des ronciers

Les graphes expanseurs de degré borné ont une largeur arborescente proportionnelle à leur nombre de sommets, et ont donc également des ronciers d'ordre linéaire. Cependant, comme l'ont montré Martin Grohe et Dániel Marx, pour ces graphes, un roncier d'un ordre aussi élevé doit contenir un nombre exponentiel d'ensembles. Plus précisément, pour ces graphes, même les ronciers dont l'ordre est légèrement supérieur à la racine carrée de la largeur arborescente doivent avoir une taille exponentielle. Cependant, Grohe et Marx ont également montré que tout graphe de largeur arborescente k admet un roncier de taille polynomiale et d'ordre $\mathrm{\Omega }(k^{1/2}/{\log }^{2}k)$.

Complexité de calcul

Étant donné que les ronciers peuvent avoir une taille exponentielle, il n'est pas toujours possible de les construire en temps polynomial pour des graphes de largeur arborescente non bornée. Cependant, lorsque la largeur arborescente est bornée, une construction en temps polynomial est possible : il est possible de trouver un roncier d'ordre k, quand il existe, en temps $O(n^{k+2})$, où n est le nombre de sommets du graphe donné. Des algorithmes encore plus rapides existent pour les graphes avec peu de séparateurs minimaux.

Bodlaender, Grigoriev et Koster ont étudié des heuristiques pour trouver des ronciers d'ordre élevé. Leurs méthodes ne génèrent pas toujours des ronciers d'ordre proche de la largeur arborescente du graphe d'entrée, mais pour les graphes planaires, elles donnent un taux d'approximation constant. Kreutzer et Tazari donnent des algorithmes randomises qui, sur des graphes de largeur arborescente k, trouvent des ronciers de taille polynomiale et d'ordre $\mathrm{\Omega }(k^{1/2}/{\log }^{3}k)$ en un temps polynomial, approchant ainsi, à un facteur logarithmique près, l'ordre dont Grohe et Marx ont montré l'existence pour les ronciers de taille polynomiale.

Ronciers orientés

La notion de roncier a également été défini epour les graphes orientésModèle:,. Dans un graphe orienté D, un roncier est une collection de sous-graphes fortement connexes de D qui sont reliés entre eux deux-à-deux : pour chaque paire d'éléments disjoints X, Y du roncier, il existe dans D un arc de X à Y et un arc de Y à X. L'ordre d'un roncier est la plus petite taille d'un ensemble de représentants, un ensemble de sommets de D qui a une intersection non vide avec chacun des éléments du roncier. Le nombre de ronces de D est l'ordre maximum d'un roncier de D. Le nombre de ronces d'un graphe orienté est, à un facteur constant près, égal à sa largeur arborescente orientée.

Notes et références

Modèle:Portail