Complexité paramétrée

En algorithmique, la complexité paramétrée (ou complexité paramétrique) est une branche de la théorie de la complexité qui classifie les problèmes algorithmiques selon leur difficulté intrinsèque en fonction de plusieurs paramètres sur les données en entrée ou sur la sortie. Ce domaine est étudié depuis les années 90 comme approche pour la résolution exacte de problèmes NP-complets. Cette approche est utilisée en optimisation combinatoire, notamment en algorithmique des graphes, en intelligence artificielle, en théorie des bases de données et en bio-informatique. En pratique, bien que les instances puissent être grandes, certaines parties des instances sont petites. L'idée est de mesurer la taille de ces parties avec un paramètre. La complexité paramétrée permet de développer des algorithmes efficaces en pratique, si on considère que le paramètre est petit. Considérons l'évaluation d'une requête dans une base de données, comme une requête SQL delete * from students where average < 18. La complexité temporelle de ce problème est en la taille de l'entrée (base de données + requête). Cependant, généralement, la base de données est énorme alors que la requête est petite. Cela tombe bien, puisque la complexité est de où est la taille de la requête et est la taille de la base de données. Ainsi, en considérant comme un paramètre, la complexité est linéaire. On dit alors que l'évaluation d'une requête dans une base de données est dans la classe FPT (fixed-parameter tractable, traduit littéralement en soluble à paramètre fixé), en prenant comme paramètre la taille de la requête.vignette|Sur cet exemple, n = 6 et k = 2. Considérons l'exemple du problème de couverture par sommets (vertex cover) d'un graphe. Étant donné un graphe, on note le nombre de sommets du graphe et la taille d'une solution, c'est-à-dire d'une couverture minimale. Fellows et Langston donnent un premier résultat de complexité paramétrée en 1986 pour ce problème. Ils montrent que l'on peut résoudre le problème en temps polynomial en si on considère comme un paramètre.