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.

Exemples et intérêt 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. Requête dans une base de données 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.

Problème de couverture par sommets Considérons l'exemple du problème de couverture par sommets () 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éeVoir , 1.3, «The Story of Dr. O, Continued» p. 5. 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. Cela signifie que, bien que le problème de couverture par sommets soit NP-complet, on peut le résoudre efficacement s'il existe des solutions petites. En d'autres termes, le problème de couverture par sommets avec la taille d'une solution comme paramètre est dans la classe FPT.

Plus précisément, Fellows et Langston remarquèrent que la théorie autour du théorème de Robertson-Seymour permet d'obtenir un algorithme en pour ce problème.

De nombreuses améliorations ont ensuite été faites. L'un des meilleurs résultats est un algorithme en temps .

Problème de satisfiabilité Le problème de satisfiabilité, aussi appelé problème SAT, consiste à savoir si une formule de la logique propositionnelle peut être mise à vrai. Un algorithme naïf consiste à parcourir la table de vérité, et pour toute attribution des valeurs de vérité des propositions atomiques apparaissant dans la formule, de regarder si cette attribution rend la formule vraie. On obtient donc un algorithme en temps où est la taille de la formule, et est le nombre de propositions atomiques dans la formule, considéré comme un paramètre. Ainsi, si une formule contient peu de propositions atomiques, on peut considérer que le problème SAT est solvable en temps linéaire.

Le problème MAX-SAT est la version d'optimisation du problème SAT : étant donné une forme normale conjonctive F, et un entier k, peut-on satisfaire au moins k clauses de F ? Le problème MAX-SAT est NP-complet (même si les clauses contiennent au plus 2 littéraux, MAX-2SAT). Si par contre, on considère k comme un paramètre, alors MAX-SAT est dans FPT.

Techniques algorithmiques classiques

Parmi les techniques classiques permettant de construire des algorithmes FPT, on compte 1.7 «A distinctive Positive Toolkit» :

les techniques liées au théorème de Robertson et Seymour, parfois appelée (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 kernelisation, c'est-à-dire la réduction à une instance plus petite, un kernel (noyau).

Largeur arborescente

En complexité paramétrée, une quête est de trouver un bon paramètre pour un problème, afin qu'il soit dans FPT. La largeur arborescente est un paramètre qui rend de nombreux problèmes algorithmiques sur les graphes dans FPT : Le problème SAT avec la largeur arborescente du graphe d’incidence variables/clauses comme paramètre est dans FPT ; Le problème de coloration avec la largeur arborescente du graphe est dans FPT. Par contre, le problème de coloration avec le nombre de couleurs requises n'est pas dans FPT, à moins que P = NP ; en effet, le problème de coloration avec trois couleurs est déjà NP-complet Le problème de chercher un ensemble indépendant Le problème de couverture de sommets Le problème du cycle hamiltonien Le théorème de Courcelle montre que, pour toute propriété exprimable en logique monadique du second ordre, le problème de savoir si un graphe vérifie cette propriété avec la largeur arborescente comme paramètre est solvable en temps linéaire et est donc dans FPT.

Arbre de recherche borné

Larbre 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 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é . Cet algorithme part de la constatation qu'un graphe est une union de cliques si et seulement s'il ne contient aucun graphe 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 induit (en temps , 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 . Si après ces deux étapes de recherche/suppression de on ne trouve plus de , 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 cas au bout de étapes) pour déduire qu'il était impossible de trouver une solution en deux (plus généralement ) éditions d'arêtes.

Problèmes paramétrés

Idée générale En théorie de la complexité, on étudie généralement des problèmes de décision. Ce sont des problèmes qui peuvent se décrire comme une question où la réponse est oui ou non. Par exemple le problème SAT peut se décrire comme :

entrée : une formule de la logique propositionnelle question : est-ce que la formule est satisfaisable, c'est-à-dire peut-on attribuer des valeurs booléennes aux variables propositionnelles de façon à rendre la formule vraie ?

En complexité paramétrée, on étudie des problèmes paramétrés. On peut les voir comme des problèmes de décision où on précise le paramètre. Par exemple :

entrée : une formule de la logique propositionnelle paramètre : le nombre de variables propositionnelles différentes apparaissant dans la formule question : est-ce que la formule est satisfaisable ?

Formalisation La formalisation précise d'un problème paramétré s'inspire de celle d'un problème de décision. En théorie de la complexité classique, les problèmes de décision sont décrits comme des langages sur un alphabet fini, c'est-à-dire des ensembles où est un alphabet fini. Ici, un problème paramétré est défini comme un couple où : ; est une fonction calculable en temps polynomial. Étant donné une valeur de k fixée, l'ensemble des instances pour lesquelles la valeur du paramètre vaut k s'appelle une tranche (slice). Formellement, une tranche de est un ensemble pour un certain k.

Formalisation alternative D'autres sources définissent un problème paramétré comme un sous-ensemble , qui contient des couples (x, k) où x est l'instance et la seconde composante k est le paramètre. Dans la suite, on utilisera pour dénoter la valeur du paramètre correspondant à x. Des fois, pour alléger les notations, nous utiliserons aussi k pour désigner la valeur du paramètre et n pour la taille de |x|.

Classes de complexité vignette|433x433px|Relations entre les classes de complexité paramétrée (cf. Fig. 5.1 de ).Dans cette section, on passe en revue les classes de complexité majeures en théorie de la complexité paramétrée.

Classe FPT Un problème paramétré est dans la classe FPT (fixed-parameter tractable, traduit littéralement en soluble à paramètre fixé) s'il admet un algorithme qui résout le problème en temps proportionnel à , où est une fonction polynomiale, |x| est la taille de l'instance x, et est une fonction quelconque calculable.

On espère ainsi que pour des instances x avec de petites valeurs de , reste petit (même si, par exemple, est exponentiel en ) afin de résoudre rapidement le problème. La valeur prise par la fonction ne dépend que de : on bannit des fonctions comme . Pour évaluer la performance d'un tel algorithme, on néglige parfois le polynôme en la taille des données, et on étend alors la notation de Landau en pour écrire que l'algorithme peut être résolu en temps .

Il existe des définitions alternatives pour la classe FPT , par exemple le temps requis peut être remplacé par . De manière équivalente, un problème paramétré est dans la classe FPT s'il admet un noyau (kernel) (voir kernelisation).

La classe P est incluse dans FPT. De plus FPT contient tous les problèmes d'optimisation de la classe NP, qui admettent un schéma d'approximation en temps polynomial : plus précisément si le problème de décision associé au problème d'optimisation est dans NP et qu'il admet un schéma d'approximation en temps polynomial, alors le problème paramétré standard (où le paramètre est égal à la valeur à optimiser) est dans FPT (Th. 1.32 dans ).

para-NP para-NP, défini par Flum et Grohe, est la classe des problèmes paramétrés pour lesquels il existe une machine de Turing non-déterministe FPT en le paramètre k.. Selon Flum et Grohe, ce n'est pas un bon candidat pour être l'analogue de la classe NP pour des problèmes paramétrés, d'où la définition de la classe W[P].

Un problème paramétré est para-NP-complet pour des réductions FPT si, et seulement si, il existe une union finie de tranches de qui est NP-complète (Th. 2.14 de ).

Réduction FPT Un problème paramétré se réduit à un autre problème paramétré s'il existe une transformation , appelée réduction FPT telle que : si et seulement si ; est calculable par un algorithme FPT (en le paramètre ) ; Il existe une fonction calculable telle que pour toute instance .

Classe XP