Post-doc projet ANR Graphes Ordonnés, Décomposition, Algorithmes et Structure (H/F)

Missions :
La personne recrutée travaillera dans le cadre du projet ANR Graphes Ordonnés, Décomposition, Algorithmes et Structures (GODASse).

En raison de leur définition simple et de leur grande polyvalence pour modéliser des systèmes complexes, les graphes occupent une place centrale aussi bien en informatique théorique qu’en informatique appliquée. La théorie de la complexité montre que la conception d’algorithmes efficaces repose sur l’exploitation des propriétés combinatoires intrinsèques des données d’entrée. On observe souvent que les algorithmes dont le temps d’exécution est optimal comportent une étape de prétraitement consistant à doter l’entrée d’une structure supplémentaire. Dans le domaine des algorithmes sur les graphes, les ordonnancements de sommets constituent un tel enrichissement structurel, à la fois simple et important. Par exemple, dans l’algorithme de Kosaraju-Sharir, un ordre des sommets obtenu par un parcours en profondeur (Depth-First Search, DFS) est utilisé pour calculer les composantes fortement connexes d’un graphe orienté.

Fait intéressant, un ordonnancement des sommets peut révéler des propriétés utiles cachées et fournir des caractérisations de classes de graphes. Par exemple, un graphe est une forêt si et seulement s’il existe un ordre des sommets tel que chaque sommet possède au plus un voisin parmi les sommets qui le précèdent. Un autre exemple est le théorème classique de Gallai–Roy–Vitaver, qui affirme qu’un graphe est k-coloriable si et seulement s’il existe un ordre des sommets ne contenant aucun chemin orienté vers l’avant de longueur k.

Les deux exemples précédents motivent la définition des graphes ordonnés afin de fournir des caractérisations finies de classes de graphes. Un graphe ordonné est un graphe G équipé d'un ordre total sur ses sommets. Un motif (induit) est un sous-graphe (induit) ordonné d’un graphe ordonné.

Étant donné un ensemble fixé (P) de graphes ordonnés, on dit qu’un ordre sur les sommets d’un graphe est un ordre (P)-libre (ou (P)-libre induit) si le graphe ordonné correspondant exclut tout motif (ou motif induit) appartenant à (P). On remarque que le théorème de Gallai–Roy–Vitaver caractérise le nombre chromatique d’un graphe par l’existence d’un ordre des sommets excluant le chemin orienté vers l’avant comme sous-graphe ordonné.

Nous soulignons ici une dichotomie importante qui jouera un rôle central dans l’organisation de notre projet de recherche. D’une part, comme l’illustrent les exemples précédents, nous cherchons à déterminer un ordre sur les sommets d’un graphe donné afin de certifier une propriété ou de concevoir un algorithme efficace. L’étude de la manière d’ordonner un graphe constituera le thème principal du premier lot de travaux (WP1).

D’autre part, un graphe peut être muni de son propre ordre, explicite ou intrinsèque. Par exemple, lorsqu’un graphe est stocké dans un ordinateur, les adresses mémoire associées a
Voir plus sur le site emploi.cnrs.fr...