Post-Doc Projet Anr Graphes Ordonnés Décomposition Algorithmes et Structure H/F - CNRS

Description du Poste Les 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 aux sommets définissent implicitement un ordre qui peut influencer l'exécution d'un algorithme (par exemple l'ordre dans lequel les sommets sont explorés lors d'un parcours). Un ordre apparaît également lorsqu'un graphe sert à modéliser un processus temporel ou dynamique. De plus, de nombreuses classes de graphes sont définies comme des graphes d'intersection d'objets géométriques ; dans ce cas, les coordonnées de ces objets induisent naturellement un ordre sur les sommets.Fait remarquable, les graphes d'intersection constituent généralement des classes de graphes bien structurées, sur lesquelles il est souvent possible de concevoir des algorithmes efficaces pour résoudre des problèmes qui sont NP-difficiles dans le cas général. Notre deuxième lot de travaux (WP2) sera consacré à l'étude de ces graphes ordonnés.De nombreuses propriétés combinatoires ou algorithmiques des graphes peuvent être exprimées par l'exclusion d'un petit graphe. Par exemple, la planarité est équivalente à l'interdiction des deux graphes de Kuratowski comme mineurs. Les relations d'inclusion entre graphes sont donc fondamentales pour comprendre la combinatoire des classes de graphes. Parmi celles-ci, les plus classiques sont les classes monotones (fermées pour la relation de sous-graphe), les classes héréditaires (fermées pour la relation de sous-graphes induits) and les classes mineurs-closes. Les deux premières notions se généralisent directement aux graphes ordonnés, et l'analogue ordonné de la relation de mineur joue un rôle important dans ce projet. En outre, afin d'exprimer des propriétés plus générales, nous autoriserons également l'équipement d'un graphe par un ordre partiel sur ses sommets plutôt que par un ordre total. La première extension de ce type que nous considérerons est celle des arborescences ordonnées (tree-orderings), utilisées dans la définition du paramètre de profondeur arborescente (tree-depth). Comme nous le verrons, les ordres, les arborescences ordonnées, ainsi que les relations d'inclusion entre graphes ordonnés, fournissent des définitions alternatives et particulièrement simples de paramètres structurels importants tels que la largeur de chemin (path-width) et la largeur arborescente (tree-width) (voir la sous-section 1.2). Cette approche offre ainsi un point de vue inédit sur de nombreux résultats existants.La discussion précédente peut être étendue dans plusieurs directions que nous nous proposons d'explorer. Le troisième lot de travaux (WP3) est ainsi consacré aux structures ordonnées au-delà des graphes. Tout d'abord, au lieu de graphes non orientés, nous considérerons des graphes orientés ou encore des matrices, qui peuvent être vues comme des graphes (orientés) pondérés. Par ailleurs, plutôt que d'ordonner les sommets, on peut choisir d'ordonner les arêtes d'un graphe ; un autre thème de recherche portera donc sur les graphes temporels (temporal graphs). Notons que ces choix sont délibérés et que de nombreux autres prolongements auraient également pu être envisagés, notamment vers les problèmes d'ordonnancement (scheduling) ou les algorithmes en flux (streaming algorithms).Comme l'illustre la discussion précédente, les ordres peuvent être utilisés pour fournir des certificats concis d'une grande variété de propriétés de graphes. Si certains résultats connus sont explicitement formulés en termes d'ordonnancement, on constate qu'un nombre bien plus important de résultats s'inscrivent naturellement dans ce cadre. Cela constitue un indice fort que le concept de graphe ordonné et ses différentes extensions revêt une importance fondamentale et mérite une étude systématique.Bien qu'il existe déjà des résultats dispersés concernant les ordres sur les graphes et les graphes ordonnés, nous ne disposons toujours pas d'une théorie unifiée. L'objectif principal de ce projet est précisément d'établir une telle théorie, englobant à la fois les aspects structurels et algorithmiques. L'Activité - Recherche en algorithmique et théorie des graphes : études bibliographiques, production d'articles sceintifiques, participation à des conférences ou workshops internationaux du domaine...- Participation à la vie de l'équipe ALGCO (séminaire, groupes de travail...)- Participation aux workshops du projet ANR GODASse Votre Profil Compétences Etre titulaire d'un doctorat en théorie et algorithmique des graphes. Une expertise en logique, décomposition de graphes, complexité paramétrée, théorie des mineurs de graphes et théorie des ordres partiels sera utile. Votre Environnement de Travail La personne recrutée deviendra membre de l'équipe ALGCO du LIRMM. Cette équipe regroupe 12 permanents ainsi que quelques doctorants ou post-doctorants et travaille en théorie et algorithmique des graphes. Le projet GODASse est un projet collaboratif impliquant l'équipe MC2 du LIP (ENS Lyon) et l'équipe GA de l'IRIF (Paris). Rémunération et avantages Rémunération A partir de 3072€ brut mensuel ajustable en fonction de l'expérience professionnelle sur des postes de niveau équivalent Congés et RTT annuels 44 jours Pratique et Indemnisation du TT Pratique et indemnisation du TT Transport Prise en charge à 75% du coût et forfait mobilité durable jusqu'à 300€ À propos de l'offre Référence de l'offre UMR5506-CHRPAU-002 Section(s) CN / Domaine de recherche Sciences informatiques : fondements de l'informatique, calculs, algorithmes, représentations, exploitations À propos du CNRS Le CNRS est un acteur majeur de la recherche fondamentale à une échelle mondiale. Le CNRS est le seul organisme français actif dans tous les domaines scientifiques. Sa position unique de multi-spécialiste lui permet d'associer les différentes disciplines pour affronter les défis les plus importants du monde contemporain, en lien avec les acteurs du changement. Le CNRS Les métiers de la recherche