Evènement pour le groupe Séminaire du LaBRI


Date 2007-11-22  14:00-15:00
TitrePartitions régulières de graphes épars et applications 
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. 
LieuAmphi LaBRI 
OrateurPatrice Ossona de Mendez 
UrlEHESS 



Aucun document lié à cet événement.

Retour
Retour à l'index