Complexité paramétrée

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

Algorithme FPT

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)$.

Arbre de recherche borné

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

• (en) Rod Downey, M. Fellows, Parameterized complexity, New York, Springer, 1999, relié (ISBN 978-0-387-94883-6) (LCCN 97022882) [lire en ligne] 

• (en) Flum, J., Grohe, M., Parameterized Complexity Theory, Berlin, Springer, 2006 (ISBN 978-3-540-29952-3) (LCCN 2005938662) [lire en ligne] 

• (en) Rolf Niedermeier, Invitation to Fixed-Parameter Algorithms, Oxford, Oxford University Press, 2006 (ISBN 978-0-19-856607-6) (LCCN 2006296258) [lire en ligne] 

• 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

• Une introduction aux algorithmes FPT.
• Un wiki sur la complexité paramétrée (en).