Complexité paramétrée

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

En informatique, 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, en algorithmique des graphes, en intelligence artificielle, en bio-informatique...

Algorithme FPT[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)).

Par exemple, il est possible de résoudre le problème de couverture des sommets d'un graphe par un algorithme FPT 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.

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.

Références[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]