Jean-Francois CULUS

  Recherche

   Mémoire de DEA:
Mon mémoire de DEA, réalisé sous la direction d'Olivier Hudry (ENST) et intitulé: « {Méthodes de partitionnements de graphes de protéines} » consiste à analyser un jeu de données expérimentales représentant le pourcentage de séquences génomiques communes entre différentes paires de protéines. Le but consiste à classifier les protéines selon leur fonctionnalité biologique afin d'orienter la recherche des biologistes. Des données expérimentales, nous extrayons un graphe pondéré dont nous partitionnons l'ensemble des sommets afin de maximiser le poids des arêtes intra-classes et minimiser celui des arêtes inter-classes. Dans un premier temps, l'étude théorique des caractéristiques combinatoires des partitions et algorithmes envisagés nous permet d'exhiber des critères pertinents. Dans un second temps, nous réglons les paramètres des algorithmes de classification implémentés afin d'obtenir des solutions localement optimales pour les critères sélectionnés.

   Thèse :

Cette thèse, relevant des mathématiques discrètes (optimisation combinatoire et théorie des graphes) et de l'informatique fondamentale (théorie de la complexité et approximation de problèmes NP-complets) aborde des problèmes de classification, d'analyse et d'optimisation de certaines décompositions sous contraintes en vue d'étudier la structure de (grands) graphes orientés. L'étude de ces graphes, notamment issus des réseaux sociaux ou de la biologie, est un sujet en constant développement depuis une vingtaine d'années, mais force est de constater que la plupart des outils et recherches se focalisent sur les graphes non orientés. Le travail présenté ici aborde des décompositions (partitions de l'ensemble des sommets) de graphes orientés, sous des contraintes à la fois intra-classes (les classes sont acircuitiques) et inter-classes (les arcs entre deux classes doivent tous être orienté dans le même sens).
Le renforcement de la contrainte ``classes acircuitiques'' en ``classes stables'' permet de retrouver la coloration orientée comme cas particulier de la ``décomposition acricuitique'', ici introduite.

Une première série d'investigations porte sur l'analyse de la complexité de la coloration orientée.
La complexité du problème de décision k-Col (un graphe orienté donné admet-il une $k$-coloration orientée ?), établie en 2004 conclut à sa NP-complétude pour k supérieur à 4 et cela, même si l'on suppose le graphe initial connexe. C'est en employant une méthode différente de celle utilisée dans cet article que nous avons sensiblement amélioré ce résultat en montrant qu'il restait NP-complet même sur une famille excessivement restreinte (graphes orientés bipartis sans circuit et de degrés bornés). En employant un résultat relatif à la coloration de cographe dû à Golumbic, nous prouvons que la famille des graphes orientés multipartis complets est polynomiale pour ce problème.

Le fait que ce problème soit NP-complet même pour des familles très spécifiques renforce l'intérêt de son approximation, tâche entamée à cette occasion. Au moyen de réductions, en particulier avec le problème du Stable Maximum, nous avons prouvé, sous l'hypothèse que P soit différent de NP, qu'il n'existait pas d'algorithme à rapport différentiel constant permettant d'approximer le problème de trouver l'entier k minimum tel qu'un graphe orienté G admette une k-coloration orientée.

Sous une hypothèse légèrement plus forte (P différent de ZPP), ce problème n'est pas non plus approximable à rapport différentiel en O(1/n), pour tout n strictement positif. Ces résultats sont surprenants puisque les différents problèmes de colorations sur les graphes non-orientés étaient approximables à rapport différentiel constant. Aussi avons-nous un premier exemple de problème de coloration sensiblement plus difficile que ses versions non-orientées.

Une autre façon d'analyser la structure d'un graphe par ces partitions est d'utiliser des outils construits aux moyens de celles-ci. On pense alors notamment au polynôme chromatique dont l'analyse permet d'établir de nombreux liens avec d'autres indices relatifs à la structure du graphe. J'ai aussi étudié si certains résultats valables pour le polynôme chromatique admettent des analogues pour le polynôme chromatique orienté. Une première difficulté s'est alors révélée être due au formalisme existant: le seul cadre orienté ne permet pas de retrouver certains résultat tel l'interprétation des coefficients du polynôme chromatique en terme d'orientations acircuitiques due à Stanley.
C'est pourquoi il s'est avéré fécond de généraliser ces deux colorations (classique et orientée) en une coloration mixte, définie sur l'ensemble des graphes mixtes (et coïncidant, d'une part avec la coloration pour les graphes non-orientés et d'autre part avec la coloration orientée sur l'ensemble des graphes orientés).
Grâce à ce nouveau formalisme, j'ai redémontré plus simplement les relations connues vérifiées par le polynôme chromatique orienté, et aussi obtenu une interprétation de ses coefficients similaire à celle de Stanley pour certaines familles de graphes orientés. Ce même formalisme a, de plus, permis l'analyse d'un {algorithme à garantie de performance} pour le problème de la coloration orientée ({Sofsem,Tcs}). Ce résultat contrebalance en partie les résultats d'inapproximabilité sur ce problème puisqu'il nous permet d'obtenir une solution présentant une certaine qualité.

Relativement à la décomposition acircuitique, j'ai établi, dans un premier temps, la NP-complétude du problème d'optimisation consistant à trouver le plus petit entier k tel qu'un graphe orienté donné admet une k-décomposition acircuitique. Néanmoins, l'analyse d'un algorithme a montré que l'importante famille des tournois est polynomiale pour ce problème. Par un argument probabiliste, nous avons prouvé que la densité des tournois n-décomposable parmi l'ensemble des tournois aléatoires d'ordre n (i.e. quand n tend vers l'infini, la probabilité qu'un tournoi pris uniformément dans cet ensemble soit n-décomposables tend vers 1).
Focalisant alors notre attention sur la structure particulière de ces tournois, nous caractérisons les tournois Sommets-Critiques n-décomposables (la suppression d'un sommet quelconque d'un tel tournoi laisse un tournoi admettant une $(n-2)$-décomposition acircuitique) comme ceux obtenus par composition de tournois circulants.

Enfin, j'introduis la notion de {polynôme chromatique acircuitique} comme outil construit au moyen de la décomposition acircuitique. Après avoir donné un moyen de dépasser une difficulté algorithmique propre à cette décomposition, j'établis les premières propriétés qui permettent son exploitation ultérieure en vue d'étudier ses liens avec des quantités caractétistiques de la structure du graphe.

  Post-doctorat :

Dans la lignée des études que j'ai menées sur le rapport d'approximation différentiel, je m'intéresse ici à compléter les connaissances de la hiérarchie des classes d'approximations différentielles au moyen de l'étude de la version optimisation du problème Sat, central en théorie de la complexité.

Les seuls résultats alors connus sur ce sujet sont obtenus au moyen de réductions mais il existe un large fossé entre ces résultats d'approximations et les bornes d'inaproximations. Les premiers résultats trouvés sont établis par une analyse fine des solutions données par des méthodes à voisinages (on prend une solution optimum local pour un certain voisinage. 
Les précédents résultats sont alors améliorés par l'obtention d'un rapport d'approximation différentiel en $[l (l-1) ... (l-k+1)]/[(n-l) ... (n-l-k+1)] pour le problème Max k-Sat en utilisant un voisinage de taille l. Nous recherchons à présent de nouveaux résultats négatifs sur ces problèmes.