Résumé | Le concept de "tree-width" est central dans l'analyse des classes de
graphes à mineurs exclus menée par Robertson et Seymour, et a gagné
un intérêt important de par ses applications algorithmiques,
essentiellement à la suite du résultat général de Courcelle
concernant la décidabilité de propriétés exprimées en logique
du second ordre monadique pour les graphes de "tree-width" bornée.
Il est apparu que nombre de problèmes NP-complets peuvent être résolus
en temps polynomial lorsqu'ils sont restreints à une classe de
"tree-width" bornée. Néanmoins, une telle restriction est extrêmement
forte, les graphes planaires, par exemple, n'ayant pas de "tree-width"
bornée.
Une approche alternative consiste à considérer des partitions de
graphes, de manière à ce que p parties induisent un sous-graphe de
faible "tree-width". DeVos et al. ont ainsi démontré que pour toute
classe propre C fermée par mineur (i.e. toute classe fermée par
mineur qui exclue au moins un graphe) et pour tout entier p, il existe
une constante N(C,p) telle que tout graphe G dans C possède une
partition de ses sommets en au plus N(C,p) parties telle que i au plus p
de ces parties induisent un sous graphe de tree-width au plus (i-1).
Il est naturel de se demander si les parties pourraient être
choisies «plus petites» ou «plus simples».
Le "tree-depth" td(G) d'un graphe G est la hauteur minimale d'une forêt enracinée dont
la fermeture inclut G.
Cet invariant monotone par mineur est lié à la tree-width par :
tw(G)+1 < td(G) < tw(G) log n, où n est l'ordre de G. Les
classes de tree-depth borné sont particulièrement petites, dans
le sens qu'elles n'incluent qu'un nombre fini de classes
d'équivalences pour l'homomorphisme, et qu'elles excluent les longues
chaînes (à comparer avec les classes de tree-width bornée qui
excluent les grandes grilles).
Notre résultat principal est que pour toute classe propre C fermée par mineur et pour
tout entier p, il existe une constante N'(C,p) telle que tout graphe G dans C possède
une partition de ses sommets en au plus N'(C,p) parties telle que
iau plus p de ces parties induisent un sous graphe de tree-depth au plus i, le
tree-depth étant le plus grand invariant satisfaisant une telle
propriété.
Notre démonstration conduit de plus à un algorithme en
temps linéaire pour les classes d'expansion bornée
(qui peuvent être vues comme une généralisation des classes excluant
un mineur topologique).
Précisons ce que sont les classes d'expansion bornée:
Le grad de rang r d'un graphe G est défini par
NABLAr(G)=max |E(H )| / |V(H )| où
le maximum concerne tous les mineurs H de G obtenus en contractant un
ensemble de sous-graphes sommets-disjoints de rayons au plus r et en
effaçant arbitrairement des sommets et des arêtes.
Une classe de graphes C est d'expansion bornée si sup{pour G dans C de NABLAr(G)} est
fini (pour tout entier r).
Ainsi, toute classe propre fermée par mineur, toute classe de degré borné, mais aussi
toute classe composée de squelettes de
complexes simpliciaux de dimension d et d'aspect ratio borné et,
plus généralement, toute classe excluant un mineur topologique sont
des classes d'expansion bornée.
Nos résultats algorithmiques principaux concernant les classes
d'expansion bornée sont:
a.. un algorithme en temps linéaire de coloration induisant de
faibles tree-depth,
b.. un algorithme en temps linéaire de recherche et de dénombrement
des sous graphes isomorphes à un sous graphe fixé.
c.. d'un point de vue plus général, la décidabilité en temps
linéaire de propriétés du premier ordre,
d.. l'existence de séparateurs de tailles sous-linéaires pour les
classes d'expansion sous-exponentielle,
e.. l'extension des résultats sur les dualités restreintes
d'homomorphismes aux classes d'expansion bornée. |