Analyse multivariée d’algorithmes : au-delà des problèmes NP-difficiles

Lorsqu’on résout un problème à l’aide d’un ordinateur, on souhaite généralement élaborer l’algorithme le plus efficace possible. Une manière classique de mesurer l’efficacité d’un algorithme est de compter le nombre d’étapes maximum qu’il va devoir effectuer. C’est ce que l’on appelle la complexité temporelle dans le pire des cas. Elle s’exprime comme une fonction de la taille de l’entrée du problème. Prenons l’exemple d’une liste de n noms de personnes ainsi que leur âge.
Si je veux savoir s’il existe une personne ayant 50 ans, je peux tout simplement parcourir ma liste et vérifier l’âge de chacune. Un tel algorithme devra parcourir (dans le pire des cas) la liste entière, et donc effectuer n tests. On dira qu’un tel algorithme a une complexité linéaire.
Si maintenant je veux tester s’il existe deux personnes dont la somme des âges vaut 100, je peux parcourir toutes les paires possibles de personnes. Dans le pire des cas, je devrai ainsi tester les n(n-1)/2 paires possibles. On dira qu’un tel algorithme a une complexité quadratique, car ce nombre de paires est “de l’ordre de” n².
Enfin, si je veux tester s’il existe un groupe (de taille quelconque) de personnes dont la somme des âges vaut 500, je peux énumérer la liste de tous les sous-ensembles possibles, et tester à chaque fois si la somme de leurs âges vaut 500. Je devrai ainsi, toujours dans le pire des cas, tester les 2ⁿ ensembles de sous-ensembles possibles. On dira qu’un tel algorithme a une complexité exponentielle.

Les deux premiers algorithmes se rangent dans la catégorie des algorithmes dits polynomiaux, car leur complexité est une fonction polynomiale (linéaire dans le premier cas, quadratique dans le second), alors que le troisième, en revanche, est un algorithme exponentiel. Les algorithmes exponentiels sont souvent impraticables lorsque la taille de l’entrée devient grande. Pour donner un ordre d’idée, avec une liste de 265 personnes, le nombre de paires de personnes est inférieur à 35 000, ce qui est un nombre d’opérations très raisonnable pour un ordinateur. En revanche, le nombre de sous-ensembles de personnes possibles (2²⁶⁵) dépasse le nombre d’atomes dans notre univers : même si les processeurs de nos ordinateurs sont capables de faire plusieurs milliards de calculs par seconde, il faudrait plusieurs millénaires pour pouvoir venir à bout de cette énumération.

La question centrale à laquelle doit répondre l’algorithmicien est la suivante : existe-t-il un algorithme polynomial qui résout mon problème ? Malheureusement, sous une conjecture classique de l’informatique théorique (appelée P≠NP), certains problèmes (dits NP-difficiles) ne disposent pas de tel algorithme.

Un exemple de problème NP-difficile est le suivant : étant donné un réseau d’ordinateurs et un sous-ensemble de ces ordinateurs que l’on appellera les terminaux, le but est de trouver le plus petit sous-réseau qui relie l’ensemble des terminaux, afin, par exemple, qu’ils puissent communiquer entre eux sans avoir à mobiliser tous les ordinateurs du réseau pour faire passer les messages.
La NP-difficulté de ce problème implique que n’importe quel algorithme aura un temps d’exécution exponentiel en la taille du réseau (toujours sous l’hypothèse P≠NP). Cependant, il est intéressant ici de distinguer le nombre total d’ordinateurs du réseau et le nombre de terminaux. C’est l’objectif de la notion de complexité paramétrée d’un problème, qui offre un cadre théorique permettant l’analyse multivariée d’un algorithme.
Dans le cas ci-dessus, il est effectivement possible d’élaborer un algorithme dont le temps d’exécution sera exponentiel en le nombre de terminaux seulement (et polynomial en le nombre total d’ordinateurs du réseau). On dira alors que l’explosion combinatoire peut être restreinte au paramètre “nombre de terminaux”. Si dans le pire des cas ce nombre peut être du même ordre de grandeur que le nombre total d’ordinateurs du réseau, il se peut qu’en pratique il soit bien inférieur (on peut par exemple imaginer 15 terminaux dans un réseau de plusieurs milliers d’ordinateurs), ce qui implique qu’un tel algorithme a de grandes chances d’être efficace dans ce cas.

La théorie de la complexité paramétrée, née dans la fin des années 1990, a bâti un ensemble de classes de complexité permettant de distinguer les problèmes pouvant admettre des algorithmes efficaces avec certains paramètres, et ceux qui sont fortement soupçonnés de ne pas en admettre. Cette théorie offre ainsi dans un certain sens un raffinement du problème P ≠ NP et des classes de difficultés qui y sont liées.

Les paramètres considérés peuvent être de diverses natures, et correspondre parfois à des propriétés structurelles des instances d’entrée. Ceci permet de proposer une généralisation et une explication à un grand nombre de phénomènes algorithmiques bien connus. Par exemple, le problème mentionné précédemment se simplifie grandement si le réseau a une forme particulière, par exemple s’il n’a pas de cycle (on dira que c’est un arbre), ou s’il peut être représenté dans le plan sans que les liaisons entre les ordinateurs ne se croisent (on dira que c’est un graphe planaire). C’est ici qu'entre en jeu la théorie des graphes, qui utilise des outils mathématiques simples permettant de modéliser les réseaux ainsi que de nombreuses autres structures discrètes que l’on peut rencontrer en pratique.

L’un des liens entre la complexité paramétrée et les graphes est de considérer comme paramètre la distance qui sépare un graphe donné d’une classe de graphes pour laquelle un problème devient facile. Il est ainsi possible d’une part d’élaborer des algorithmes qui seront d’autant plus efficaces que la distance considérée est petite, et d’autre part de pouvoir généraliser des algorithmes connus pour des ensembles d’instances plus importants. Tout ceci fait appel à des outils puissants de la théorie structurale des graphes, tels que la notion de largeur arborescente.

Cette stratégie fait partie des recherches développées au sein de l’équipe MC2 : étudier les propriétés structurelles des graphes dans le but de développer des outils algorithmiques permettant d’améliorer et de classifier la complexité de problèmes combinatoires difficiles.

Publications :

• Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, Rémi Watrigant : Parameterized Complexity of Independent Set in H-Free Graphs. CoRR abs/1810.04620 (2018)
• Nicolas Bousquet, Jean Daligault, Stéphan Thomassé : Multicut Is FPT. SIAM J. Comput. 47(1) : 166-207 (2018)
• Stéphan Thomassé, Nicolas Trotignon, Kristina Vuskovic : A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs. Algorithmica 77(3) : 619-641 (2017)