Complexité paramétrée

Considérons l'évaluation d'une requête dans une base de données[2], comme une requête SQL delete * from students where average < 18. La complexité temporelle de ce problème est exponentielle 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 ${\displaystyle O(2^{k}n)}$ où ${\displaystyle k}$ est la taille de la requête et ${\displaystyle n}$ est la taille de la base de données. Ainsi, en considérant ${\displaystyle 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.

Considérons l'exemple du problème de couverture par sommets (vertex cover) d'un graphe. Étant donné un graphe, on note ${\displaystyle n}$ le nombre de sommets du graphe et ${\displaystyle 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[3] en 1986 pour ce problème. Ils montrent que l'on peut résoudre le problème en temps polynomial en ${\displaystyle n}$ si on considère ${\displaystyle 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 ${\displaystyle O(f(k)n^{3})}$ pour ce problème[4].

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

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 ${\displaystyle O(2^{k}n)}$ où ${\displaystyle n}$ est la taille de la formule, et ${\displaystyle 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[6].

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[8] :

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

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 ${\displaystyle 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é ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle P_{3}}$ induit (en temps ${\displaystyle 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 ${\displaystyle P_{3}}$. Si après ces deux étapes de recherche/suppression de ${\displaystyle P_{3}}$ on ne trouve plus de ${\displaystyle 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 ${\displaystyle 3^{k}}$ cas au bout de ${\displaystyle k}$ étapes) pour déduire qu'il était impossible de trouver une solution en deux (plus généralement ${\displaystyle k}$) éditions d'arêtes.

Un problème paramétré ${\displaystyle (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 à ${\displaystyle f(\kappa (x))\times poly(|x|)}$, où ${\displaystyle poly(.)}$ est une fonction polynomiale, |x| est la taille de l'instance x, et ${\displaystyle f}$ est une fonction quelconque calculable[10].

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

Il existe des définitions alternatives pour la classe FPT , par exemple le temps requis peut être remplacé par ${\displaystyle 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 elle 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 [9]).

para-NP, défini par Flum et Grohe[11], est la classe des problèmes paramétrés ${\displaystyle (Q,\kappa )}$ pour lesquels il existe une machine de Turing non-déterministe FPT en le paramètre k[12]. Selon Flum et Grohe[9], 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 ${\displaystyle (Q,\kappa )}$ qui est NP-complète (Th. 2.14 de [9]).

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

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

On définit la classe XP non uniforme comme la classe des problèmes paramétrés dont chaque tranche est dans PTIME[12]. 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 ${\displaystyle O(n^{f(k)}+f(k))}$ où ${\displaystyle f}$ est une fonction calculable[12]. 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 nk é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 [9]).

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 [9]). 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[14] - [15] 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).p(n) étapes de calcul, avec au plus h(k) log n étapes de calcul non-déterministes, où 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. La hiérarchie W est définie comme suit. Un problème paramétré est dans W[i] si toute instance ${\displaystyle (x,k)}$ peut être transformée (en temps FPT) en un circuit logique de weft au plus i, tel que ${\displaystyle (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 ${\displaystyle W[i]\subseteq W[j]}$ pour tout ${\displaystyle 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[6]. 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[6]. Weighted-c-CNF-SAT est W[1]-complet pour toute constante ${\displaystyle 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.

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

• (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.

• 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

• Kernelisation
• Chaîne la plus proche