Stéphan Thomassé : « Disséquer les graphes pour mieux combiner leurs algorithmes de résolution »

Pour débuter, pouvez-vous rappeler ce qu’est un graphe, et comment ils peuvent aider à résoudre des problèmes ?

Stéphan Thomassé : Les graphes, ces ensembles de points, appelés « sommets », qui sont reliés par des arêtes, permettent de représenter différentes choses, comme un réseau social ou un plan de circulation urbaine… Pour résoudre certaines problématiques, il est possible de conceptualiser l’objet étudié sous forme d’un graphe qui devient ainsi un objet informatique que l’on peut manipuler. Il devient ainsi possible d’y appliquer un algorithme, c’est-à-dire une suite d’actions, en vue de la résolution d’une problématique donnée. Le souci est que jusqu’à maintenant, il est très difficile de déterminer quel type de graphe fait appel à quel algorithme. 

Il existe des problèmes « classiques » en algorithmique de graphes, comme le voyageur de commerce, où l’on souhaite parcourir tous les sommets par le circuit le plus court ; ou la coloration de graphes, où l’on cherche le nombre minimum de couleurs à affecter aux sommets de sorte que deux sommets adjacents soient de couleurs différentes ; ou encore le stable maximal, où l’on recherche un sous-ensemble de sommets sans arêtes communes le plus grand possible. Tous ces problèmes ont été très étudiés depuis le début de l’algorithmique dans les années 1960 et font partie des 21 premiers problèmes durs (NP-difficiles) historiques. Il n’existe pas, et il est très improbable qu’il existe un jour, d’algorithmes de résolution efficaces, appelés polynomiaux, de ces problématiques. Cependant, comme ces problèmes permettent de modéliser facilement d’autres problématiques, la communauté continue de s’y intéresser.

Jusqu’à maintenant, comment procède-t-on pour trouver le bon algorithme pour le bon graphe ?

S. T. : Tous les graphes ne se ressemblent pas, ils ont des propriétés additionnelles qui permettent d’orienter le choix de l’algorithme. Il existe par exemple la classe des graphes planaires, que l’on peut dessiner sur un plan sans que des arêtes se croisent, comme un graphe de pays. Ou bien des graphes bipartis, qui possèdent deux classes de sommets, comme par exemple des clients et des taxis, et où l’algorithme devra affecter de manière dynamique un taxi au client le plus proche. Ou encore les graphes denses ou au contraire épars, qui ont respectivement beaucoup ou très peu d’arêtes… 

C’est en fonction de ces propriétés que l’on va choisir une tactique de résolution, généralement choisies dans trois grandes classes. Les méthodes géométriques, efficaces sur les graphes bipartis, emploient un objet mathématique appelé polytope, sorte de gros diamant à multiples facettes. Chaque solution du graphe est représentée par un sommet du polytope, et la solution optimale se distingue par le sommet le plus éloigné dans une direction donnée. 
Une autre technique fait appel à la décomposition arborescente, appliquée le plus souvent pour les graphes de faible largeur. On découpe le graphe en différentes parties que l’on peut ainsi résoudre par fractions, en appliquant un principe de diviser pour mieux régner. On emploie ensuite la programmation dynamique pour recombiner les solutions partielles. 
Enfin, l’approximation statistique se base sur le fait de sélectionner une information réduite d’un graphe pour le traiter. En approchant le graphe par une structure simplifiée, cela permet de traiter ainsi une approximation plutôt que le graphe en entier. Cette méthode fonctionne généralement bien sur les graphes denses. 
D’autres méthodes existent, mais dans le principe on associe donc un type particulier d’algorithmes à une classe de graphes.

Quel est votre apport dans cette recherche algorithmique sur les graphes ?

S. T. : Actuellement, il y a une méconnaissance complète de ce qui fait qu’un algorithme fonctionne sur un type de graphe ou non. Il y a des cas où une approche résout la problématique, comme la méthode géométrique qui permet de trouver une coloration optimale sur un graphe parfait, mais où on ne comprend pas le fonctionnement. À l’inverse, certaines techniques éclairent le fonctionnement de la structure mais ne fournissent pas d’algorithme. Je travaille sur une prise de recul sur ces techniques, pour pouvoir les combiner. Une compréhension générale des algorithmes de résolution serait peine perdue, mais en se plaçant dans des cas particuliers je cherche à comprendre pourquoi certaines méthodes fonctionnent, et à trouver des liens entre elles. Je souhaite ainsi mettre de la compréhension sur de l’efficacité. 

De plus, dès lors que l’on est dans une classe de graphes particulière, il y a des propriétés associées qui ne sont pas nécessairement exploitées. L’hypothèse de se trouver dans une classe particulière de graphes ne donne-t-elle pas à elle seule déjà de la structure ? Une question ouverte de théorie des graphes posée par Erdos et Hajnal affirme que dès lors que l’on se trouve dans une classe particulière de graphes, alors la taille maximale d’un stable ou d’une clique (ensemble de sommets reliés 2 à 2 par arête) est considérablement plus grande que ce que l’on pourrait attendre dans le cas général (polynomial plutôt que logarithmique). À elle seule, cette question (si validée) indique qu’il nous manque un outil essentiel dans la compréhension des classes de graphes, outil qui pourrait s’avérer un précieux atout algorithmique. En cherchant ces nouvelles méthodes, ces nouveaux outils, je souhaite trouver des indices fermes à travers les questions ouvertes.