Complexité paramétrée

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique théorique, et plus précisément en algorithmique, la complexité paramétrée est une mesure de la complexité d'un problème en fonction de plusieurs paramètres, et pas seulement la taille totale des données en entrée. Elle est étudiée depuis les années 90 comme approche pour la résolution exacte de problèmes NP-complets. Les algorithmes FPT sont utilisés pour résoudre des problèmes d'optimisation combinatoire notamment en algorithmique des graphes, en intelligence artificielle et en bio-informatique.

Définition et intérêt[modifier | modifier le code]

Un algorithme est dit FPT en un paramètre k (fixed-parameter tractable, traduit littéralement en soluble à paramètre fixé) s'il permet de résoudre un problème paramétré par k en temps proportionnel à f(k).poly(n)), où poly(n) est une fonction polynomiale en la taille des données du problème, et f est une fonction quelconque.

On espère ainsi que pour de petites valeurs de k, f(k) restera petit (même si exponentiel en k) et on pourra résoudre rapidement le problème. L'exponentielle portant sur k et pas sur la taille des données du problème, c'est cette fonction f(k) qu'on va tenter d'optimiser avec l'approche de complexité paramétrée. Ainsi, pour évaluer la performance d'un algorithme FPT, on néglige parfois le polynôme en la taille des données, et on étend alors la notation de Landau pour écrire que l'algorithme peut être résolu en temps O^*(f(k)).

Exemple[modifier | modifier le code]

Par exemple, il est possible de résoudre le problème de couverture par sommets (vertex cover) d'un graphe par un algorithme FPT. Le premier résultat dans ce sens[1] date de 1986, quand Fellows et Langston remarquèrent que la théorie autour du théorème de Robertson-Seymour permettait d'obtenir un algorithme en O(f(k)n^3) pour ce problème[2]. De nombreuses améliorations ont ensuite été faites[1]. L'un des meilleurs résultat est un algorithme en temps O^*(1.274^k), ou plus précisément O(kn+1.274^k), où k est la taille de la solution et n le nombre de sommets du graphe[3].

Classes de complexité[modifier | modifier le code]

On peut définir des réductions et des classes de complexité dans le contexte de la complexité paramétrée. Il existe notamment une hiérarchie des problèmes, appelée hiérarchie W, liée aux circuits booléens (ou aux formules 3-SAT associées)[4],[5].

Techniques algorithmiques classiques[modifier | modifier le code]

Parmi les techniques classiques permettant de construire des algorithmes FPT, on compte[6] :

  • les techniques liées au théorème de Robertson et Seymour, parfois appelée Well-quasi-ordering techniques (techniques de beaux ordres en traduction littérale), donnant des résultats d'existence peu utilisables en pratique;
  • l'utilisation de décompositions de graphes comme la décomposition arborescente avec la largeur d'arbre comme paramètre associé;
  • le color coding (hashing)
  • des méthodes plus élémentaires comme les arbres de recherches bornés ou la réduction à un kernel (noyau).

Arbre de recherche borné[modifier | modifier le code]

L'arbre de recherche borné est une stratégie classique de conception d'algorithmes FPT. Il s'agit de localiser un ensemble de conflits qui empêche de résoudre le problème, et d'essayer de régler chaque conflit avec un nombre borné de façons possibles.

Par exemple, le problème Cluster Editing, utile en partitionnement de données, qui consiste à faire le minimum d'ajouts et suppressions d'arêtes dans un graphe pour obtenir une union de cliques disjointes, est NP-complet. En appelant k le nombre d'ajouts et de suppressions impliqués dans la solution optimale, ce problème se résout par un algorithme FPT en arbre de recherche borné de complexité O(3^k n^3). Cet algorithme part de la constatation qu'un graphe est une union de clique si et seulement s'il ne contient aucun graphe P_3 induit, c'est-à-dire un ensemble de 3 sommets qui ne contient que 2 arêtes (un sommet est relié aux deux autres, qui sont indépendants). La stratégie consiste donc à identifier un graphe P_3 induit (en temps O(n^3), en testant tout ensemble de trois sommets), et à le supprimer de trois façons possibles : soit en supprimant une arête entre deux sommets adjacents (deux possibilités), soit en ajoutant une arête entre les deux sommets indépendants. On obtient donc trois graphes, sur lesquels on applique à nouveau cette recherche et suppression de P_3. Si après ces deux étapes de recherche/suppression de P_3 on ne trouve plus de P_3, on a trouvé une solution en deux éditions d'arêtes qui permettent de régler le problème. Sinon, on a examiné au total 9 cas (ou plus généralement 3^k cas au bout de k étapes) pour déduire qu'il était impossible de trouver une solution en deux (plus généralement k) éditions d'arêtes.

Notes et références[modifier | modifier le code]

  1. a et b Voir Downey et Fellows 1999, 1.3, «The Story of Dr. O, Continued» p. 5.
  2. Michael R Fellows et Michael A Langston, « Nonconstructive advances in polynomial-time complexity », Information Processing Letters, Elsevier, vol. 26, no 3,‎ 1987, p. 157-162
  3. Jianer Chen, Iyad A. Kanj et Ge Xia, « Improved Parameterized Upper Bounds for Vertex Cover », dans MFCS 2006, vol. 4162,‎ 2006 (lien DOI?), p. 238-249
  4. Downey et Fellows 1999
  5. (en) La classe W[t sur le Complexity Zoo]
  6. Downey et Fellows 1999 1.7 «A distinctive Positive Toolkit»

Bibliographie[modifier | modifier le code]

  • The Computer Journal. Volume 51, Numbers 1 and 3 (2008). Double numéro spécial sur la complexité paramétrée de 15 articles, édité par R. Downey, M. Fellows et M. Langston.

Liens externes[modifier | modifier le code]