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.

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 exponentielle^{[Information douteuse][réf. nécessaire]} 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(2^{k}n)$ où $k$ est la taille de la requête et $n$ est la taille de la base de données. Ainsi, en considérant $k$ 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.

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 (vertex cover) d'un graphe. Étant donné un graphe, on note $n$ le nombre de sommets du graphe et $k$ 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 $n$ si on considère $k$ 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 $O(f(k)n^{3})$ pour ce problème.

De nombreuses améliorations ont ensuite été faites. L'un des meilleurs résultats est un algorithme en temps $O(kn+1,274^{k})$.

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(2^{k}n)$ où $n$ est la taille de la formule, et $k$ 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 :

• 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 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é

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 cliques 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.

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 $Q\subseteq \Sigma ^{*}$ où $\Sigma$ est un alphabet fini. Ici, un problème paramétré est défini comme un couple $(Q,\kappa )$ où :

• $Q\subseteq \Sigma ^{*}$;
• $\kappa :\Sigma ^{*}\rightarrow \mathbb {N}$ 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 $(Q,\kappa )$ est un ensemble $\{x\in Q\mid \kappa (x)=k\}$ pour un certain k.

Formalisation alternative

D'autres sources définissent un problème paramétré comme un sous-ensemble $L\subseteq \Sigma ^{*}\times \mathbb {N}$, 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 $\kappa (x)$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é

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é $(Q,\kappa )$ 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 à $f(\kappa (x))\times poly(|x|)$, où $poly(.)$ est une fonction polynomiale, |x| est la taille de l'instance x, et $f$ est une fonction quelconque calculable.

On espère ainsi que pour des instances x avec de petites valeurs de $\kappa (x)$, $f(\kappa (x))$ reste petit (même si, par exemple, $f(\kappa (x))$ est exponentiel en $\kappa (x)$) afin de résoudre rapidement le problème. Notez que la valeur prise par la fonction $f$ ne dépend que de $k$ : on bannit des fonctions $f(|x|,\kappa (x))$ comme $|x|^{\kappa (x)}$. 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 $O(.)$ en $O^{*}(.)$ pour écrire que l'algorithme peut être résolu en temps $O^{*}(f(\kappa (x)))$.

Il existe des définitions alternatives pour la classe FPT , par exemple le temps requis peut être remplacé par $f(\kappa (x))+poly(|x|)$. 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 $(Q,\kappa )$ 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 $(Q,\kappa )$ qui est NP-complète (Th. 2.14 de ).

Réduction FPT

Un problème paramétré $(Q,\kappa )$ se réduit à un autre problème paramétré $(Q',\kappa ')$ s'il existe une transformation $R:x\mapsto R(x)$, appelée réduction FPT telle que :

• $x\in Q$ si et seulement si $R(x)\in Q'$;
• $R$ est calculable par un algorithme FPT (en le paramètre $\kappa$) ;
• Il existe une fonction calculable $g:\mathbb {N} \rightarrow \mathbb {N}$ telle que $\kappa '(R(x))\leq g(\kappa (x))$ pour toute instance $x$.

Classe XP

On définit la classe XP non uniforme comme la classe des problèmes paramétrés dont chaque tranche est dans PTIME. Cette classe est étrange dans le sens où elle contient des problèmes indécidables. C'est pourquoi l'on définit la classe XP dite uniforme, ou plus simplement la classe XP, qui contient les problèmes qui peuvent être résolus en temps $O(n^{f(k)}+f(k))$ où $f$ est une fonction calculable. La classe a un rôle similaire en théorie de la complexité paramétrée à la classe EXPTIME en théorie de la complexité classique : le problème de savoir si M s'arrête sur le mot vide en moins de n^k étapes, étant donné une machine de Turing déterministe M, n écrit en unaire et un entier k, avec k paramètre est XP-complet (avec réductions FPT) (cf. Th. 2.25 dans ).

Hiérarchie W

Trame en tissage, weft en anglais, qui a donné le nom à la hiérarchie W.

Avant de définir la hiérarchie W, définissons la classe W[P] qui est l'union de toutes les classes de la hiérarchie W. La classe W[P] peut être vue comme la version paramétrée de la classe NP. Selon Flum et Grohe, c'est une des classes de complexité paramétrée les plus importantes (cf. p. 45 de ). La lettre W vient du mot weft (terminologie en textile, trame en français) et la lettre P dans "W[P]" est pour "polynomial". La hiérarchie W est une suite de classes de complexité W[0], W[1], etc. dont la définition est basé sur le weft d'un circuit booléen.

Un problème paramétré est dans W[P] s'il est décidé par une machine de Turing non-déterministe en au plus $f(k)\times p(n)$ étapes de calcul, avec au plus $h(k)\times \log n$ étapes de calcul non-déterministes, où f$f$, $h$ sont des fonctions calculables et $p$ est un polynôme ($n$ est la taille de l'entrée, et $k$ la valeur du paramètre).

Le weft d'un circuit booléen est le nombre maximal de portes avec au moins 3 entrées sur tout chemin de la racine à une feuille^[pas clair]. La hiérarchie W est définie comme suit. Un problème paramétré est dans W[i] si toute instance $(x,k)$ peut être transformée (en temps FPT) en un circuit logique de weft au plus i et de profondeur au plus constante, tel que $(x,k)\in L$ si et seulement si il existe une assignation des entrées qui satisfait le circuit et qui assigne 1 à au plus k entrées. On a W[0] = FPT et $W[i]\subseteq W[j]$ pour tout $i\leq j$.

Le problème Bounded-CNF-SAT (étant donné une forme normale conjonctive, et k un entier, est-elle satisfaite par une assignation avec au plus k variables mises à vraies ?) est W[2]-complet. Le problème Bounded-3CNF-SAT (le même problème mais restreint au forme normale conjonctive avec au plus 3 littéraux par clause, comme dans le problème 3-SAT) est par contre dans FPT. Le problème Weighted-CNF-SAT (étant donné une forme normale conjonctive, et k un entier, est-elle satisfaite par une assignation avec exactement k variables mises à vraies ?) est W[2]-complet. Weighted-c-CNF-SAT est W[1]-complet pour toute constante $c\geq 2$.

W[SAT] est l'analogue de W[P] mais sur des formules propositionnelles au lieu des circuits. Un problème complet pour W[SAT] est le problème :

• entrée : une formule propositionnelle monotone (le fait de la supposer monotone n'est pas important pour la dureté) phi, un entier k
• sortie : oui, si en mettant au plus k variables à vrai, on peut rendre phi vraie ; non sinon.

W[1] est la restriction de W[SAT] à des formules CNF. W[2] est la restriction de W[SAT] à des conjonctions de disjonctions de conjonctions de littéraux.

Hiérarchie A

Il existe une autre hiérarchie, la hiérarchie A, qui est le pendant de la hiérarchie polynomiale mais en complexité paramétrée. On a A[1] = W[1].

Histoire

La classe FPT (fixed-parameter tractability) a été introduite par Downey et Fellows. Le prix IPEC Nerode de l'EATCS récompense les articles exceptionnels en complexité paramétrée depuis 2013.

Voir aussi

Bibliographie

• (en) Rod Downey et M.R. Fellows, Parameterized complexity, New York, Springer, 1999, 533 p. (ISBN 978-0-387-94883-6, LCCN 97022882)
• (en) Rod Downey et M. R. Fellows, Fundamentals of Parameterized Complexity, London u.a., Springer, 2013, 763 p. (ISBN 978-1-4471-5559-1, lire en ligne)
• (en) J. Flum et M. Grohe, Parameterized Complexity Theory, Berlin, Springer, 2006 (ISBN 978-3-540-29952-3, LCCN 2005938662)
• (en) Rolf Niedermeier, Invitation to Fixed-Parameter Algorithms, Oxford, Oxford University Press, 2006, 316 p. (ISBN 978-0-19-856607-6, LCCN 2006296258)
• (en) Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michał Pilipczuk et Saket Saurabh, Parameterized Algorithms, 2015, xvii+ 613 (ISBN 978-3-319-35702-7)
• 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).
• Christophe Paul, « Complexité parametree (3) Réductions paramétrées et classes de complexité », 2010

Articles connexes

• Kernelisation
• Chaîne la plus proche