Thèmes de Recherche: Théorie des graphes, Optimisation Combinatoire, Complexité et Approximation.

Recherche: Nous nous intéressons à un problème de partitionnement de graphes orientés en classes acycliques avec une contrainte supplémentaire d'unidirection entre les classes.
Situation du problème: Des travaux de Bojan Mohar [circular chromatic number] étudient la décomposition de graphes orientés en classes acycliques, mais sans contrainte d'unidirection, alors que la notion de coloration orienté, définie par Eric Sopena [Oriented chromatic number] utilise-elle l'unidirection entre des classes stables. Notre décomposition se trouve donc être médiane entre ces deux problèmes et nous nous inspirons des résultats de l'un comme de l'autre pour étudier notre problème. Les travaux de Pierre Ille, sur une notion de "décomposition" [indecomposable graph], se trouvent eux aussi étonnamment proche de notre notion de décomposition, puisqu'il s'agit d'une contrainte d'unidirection entre des classes quelconques.
La complexité de ce problème nous est connue, puisqu'il est NP-complet, mais nous disposons d'un algorithme polynomial dans le cas des tournois.
Une remarque probabiliste fait que nous savons que la probabilité d'obtenir des tournois "indécomposables" (classes triviales) tends vers 1 quand le nombre de sommets du tournoi tend vers l'infini. Ainsi nous sommes nous intéressé à une notion d'irréductibilité relative à cette décomposition, et nous sommes en mesure de caractérisé exactement de tels tournois (présentation SFC2004 à Bordeaux et soumis à publication auprès de Discrete Mathematics).
Travaux en cours: Nous suivons donc actuellement plusieurs voies:
    Recherche d'algorithmes garantissant une certaine performance pour ce problème ou pour celui, très proche, du nombre chromatique orienté.
    Recherche de caractérisation du nombre de décomposition étendu aux graphes non orienté (en considérant l'ensemble des orientations possibles de ce graphe).
    Problématique "On line", c'est à dire lorsque la totalité de l'instance ne nous est pas connue initialement, mais que nous découvrions le graphe sommet après sommet et devons alors attribuer au nouveau sommet une classe de manière irréversible. Il est donc aisé de voir que l'on ne peut obtenir d'algorithme déterministe non trivial garantissant ne serait-ce que l'obtention d'une solution réalisable pour toute instance. Ainsi, il semblerait que le seul moyen d'étudier cette intéressante problématique soit de le faire au moyen d'algorithmes probabilistes...
    Problématique du "feedback arc set". Ce problème, fort étudié, est lié au notre. En effet, une résolution exacte de notre décomposition serait un pré traitement des instances du problème FAS. Pour l'heure, il ne semble pas y avoir le lien mathématiques prouvable entre ces deux problèmes, mais nous étudions néanmoins un algorithme relatif au FAS qui, nous l'espérons pour l'heure, garantisse une approximation différentielle du FAS.

Centres d'intérêts:

• Théorie des graphes, et plus généralement mathématiques discrètes. (pour modéliser des problèmes réels).
• Problèmes de combinatoire relatifs au partitionnement d'un graphe (car des phénomens combinatoires peuvent intervenir dans la résolution).
• Complexité algorithmique (parceque certains problèmes sont trop difficile pour les pauvres ordinateurs dont nous disposons). 
• Approximation algorithmique (où comment résoudre le moins mal possible un problème trop difficile pour être exactement résolu).
• Outils logiques (parceque cela ne fait jamais de mal de faire de la logique).