Kernelisation

En informatique théorique, et notamment en théorie de la complexité, la kernelisation ou réduction au noyau est une formalisation d'un prétraitement efficace d'une instance d'un problème NP-difficile qui consiste à l'alléger et à le simplifier. La réduction se place dans le cadre de la complexité paramétrée.

La réduction est possible quand une instance d'un problème possède des parties qui sont facilement décidables et détectables, et que l'on peut enlever sans modifier le problème de départ. Les données qui subsistent après ces réductions forment le noyau de l'instance.

Exemples[modifier | modifier le code]

Avant de donner une définition formelle, des exemples typiques :

Coloration de graphes

Dans une instance du problème de coloration de graphe avec q couleurs, on peut successivement enlever les sommets x dont le degré est inférieur à q puisque, dans une coloration en q couleurs du reste du graphe, le voisinage du sommet x contient au plus q-1 couleurs, ainsi il reste toujours une couleur de disponible pour colorer x. Par conséquent, le graphe de départ est colorable en q couleurs si et seulement si le graphe obtenu par suppression du sommet x l’est.

Problème de couverture par sommets

Dans une instance (G,k) du problème de couverture par sommets (qui consiste en la recherche d'une couverture par k sommets) on peut choisir successivement des sommets x dont le degré est plus grand que k. En effet ces sommets font nécessairement partie d'une couverture par sommets parce que les arêtes incidentes à x doivent être couvertes, et si x ne fait pas partie de la couverture, tous les sommets de son voisinage doivent en faire partie ; s'il y a plus de k voisins, la borne de k serait dépassée. Ainsi, G possède une couverture de taille au plus k si le graphe privé de x possède une couverture de taille au plus k-1.

Problème de la clique

Dans une instance G du problème d'existence d'une clique de q sommets, on peut supprimer successivement des sommets x dont le degré est strictement plus petit que q-1, parce que les sommets d'une clique de taille q sont voisins des autres q-1 sommets de la clique ce qui implique qu'ils sont de degré au moins q-1. Ainsi, G possède une clique de taille q exactement si le graphe privé de x en possède une.

Définition formelle[modifier | modifier le code]

Deux formulations proches ont été proposées :

Formulation de Downey et Fellows[modifier | modifier le code]

Pour Downey et Fellows 1999, un problème paramétré est une partie ${\displaystyle L\subseteq \Sigma ^{*}\times \mathbb {N} }$ qui décrit un problème de décision.

Une kernelisation pour un problème paramétré ${\displaystyle L}$ est un algorithme qui prend une instance ${\displaystyle (X,k)}$ et la transforme, en temps polynomial en la taille n de ${\displaystyle X}$ et de la valeur ${\displaystyle k}$ en une instance ${\displaystyle (X',k')}$ avec les propriétés suivantes :

• ${\displaystyle (X,k)}$ est dans ${\displaystyle L}$ si et seulement ${\displaystyle (X',k')}$ est dans ${\displaystyle L}$,
• la taille de ${\displaystyle X'}$ est majoré par une fonction calculable ${\displaystyle f}$ en ${\displaystyle k}$,
• ${\displaystyle k'}$ est majoré par une fonction en ${\displaystyle k}$ indépendante de ${\displaystyle n}$.

Le résultat ${\displaystyle (X',k')}$ de la kernelisation est appelé le noyau. La taille de ${\displaystyle X'}$ est ici juste sa longueur comme chaîne de symboles ; on peut aussi considérer le nombre de sommets ou le nombre d'arêtes, dans le contexte de problèmes sur les graphes.

On dit que le problème admet un noyau polynomial si ${\displaystyle k'=k^{O(1)}}$, et un noyau linéaire si ${\displaystyle k'=O(k)}$. Si on trouve un tel algorithme, alors on sait résoudre le problème de départ en temps ${\displaystyle h(f(k))+n^{O(1)}}$, où ${\displaystyle h}$ est le coût d’un algorithme de résolution du problème non paramétré et où le terme ${\displaystyle n^{O(1)}}$ correspond au coût polynomial de la réduction^[1].

Formulation de Flum et Grohe[modifier | modifier le code]

Pour Flum et Grohe 2006, p. 4, un problème paramétré est composé d'un problème de décision ${\displaystyle L\subseteq \Sigma ^{*}}$ et d'une fonction ${\displaystyle \kappa :\Sigma ^{*}\to \mathbb {N} }$, la paramétrisation. Le paramètre d'une instance ${\displaystyle X}$ est le nombre ${\displaystyle \kappa (X)}$.

Une kernelisation pour un problème paramétré ${\displaystyle L}$ est un algorithme qui prend une instance ${\displaystyle X}$ avec paramètre ${\displaystyle k}$ et la transforme, en temps polynomial en une instance ${\displaystyle Y}$ avec les propriétés suivantes :

• ${\displaystyle X}$ est dans ${\displaystyle L}$ si et seulement si ${\displaystyle Y}$ est dans ${\displaystyle L}$ et
• la taille de ${\displaystyle Y}$ est majorée par une fonction calculable ${\displaystyle f}$ en ${\displaystyle k}$.

Dans cette formulation, la borne sur la taille de ${\displaystyle Y}$ implique que le paramètre de ${\displaystyle Y}$ est aussi majoré par une fonction en ${\displaystyle k}$.

La fonction ${\displaystyle f}$ est fréquemment appelée la taille du noyau. Si ${\displaystyle f(k)=k^{O(1)}}$, on dit que ${\displaystyle L}$ possède un noyau polynomial. De même, si ${\displaystyle f={O(k)}}$, le problème possède un noyau linéaire.

Remarque[modifier | modifier le code]

Dans la formulation de la réduction, le problème de départ n'est pas forcément décidable ou récursivement énumérable. Par exemple, la suppression d'états inaccessibles dans une machine de Turing répond formellement à la définition d'une réduction au noyau pour la question (indécidable) de savoir si la fonction calculée par la machine de Turing est une fonction partielle.

Exemples (suite)[modifier | modifier le code]

Problème de couverture par sommets (suite)

Donnée: un graphe G = (V, E) et un entier k.
Problème: existe-t-il un ensemble de k sommets couvrants ?

On commence par supprimer les boucles et arêtes multiples, puis on supprime itérativement les sommets de degré ${\displaystyle k}$ qui sont nécessairement dans l'ensemble ouvrant. Le graphe restant n’a que des sommets de degré ${\displaystyle \leq k}$. Il a donc ${\displaystyle \leq k^{2}}$ arêtes, sinon il ne peut pas être couvert par ${\displaystyle k}$ sommets de degré ${\displaystyle \leq k}$. Il reste donc au plus ${\displaystyle 2k^{2}}$ sommets non isolés : on a extrait un noyau de taille ${\displaystyle O(k^{2})}$ en temps ${\displaystyle O(n+m)}$. Avec la stratégie des arêtes on obtient un algorithme en ${\displaystyle O(n+m+2^{k}k^{2})}$^[1]. Un algorithme brute-force opère en temps ${\displaystyle O(n+m+2^{2k^{2}})}$ ce qui est toujours encore raisonnable pour un petit k, et de grandes valeurs de n et m.

Coupe-cycles de sommets

Le problème du coupe-cycles de sommets possède un noyau de ${\displaystyle 4k^{2}}$ sommets et ${\displaystyle O(k^{2})}$ arêtes^[2].

FPT et kernelisation[modifier | modifier le code]

Un problème paramétré est un langage formel ${\displaystyle L\subseteq \Sigma ^{*}\times \mathbb {N} }$, où ${\displaystyle \Sigma }$ est un alphabet fini ; la deuxième composante ${\displaystyle k}$ d'une instance ${\displaystyle (X,k)\in \Sigma ^{*}\times \mathbb {N} }$ est appelé son paramètre. Un problème ${\displaystyle L\subseteq \Sigma ^{*}\times \mathbb {N} }$ est fixed-parameter-tractable s'il admet un algorithme qui, à paramètre fixé, décide d'une instance ${\displaystyle (X,k)}$ de ${\displaystyle L}$ en temps ${\displaystyle f(k)\cdot n^{O(1)}}$, où n est la taille de X, et où f est une fonction calculable. La classe des problèmes fixed-parameter-tractable est notée FPT.

Tout problème décidable paramétré, pour lequel on sait que la taille du noyau de chaque instance (X,k) est majorée par f(k) pour une fonction f, est fixed-parameter-tractable, parce que l'on peut, après la réduction, appliquer au noyau un algorithme de complexité en temps h, ce qui donne une complexité en temps ${\displaystyle n^{O(1)}+h(f(k))}$.

Réciproquement, on peut démontrer que toute instance (X,k) d'un problème fixed-parameter-tractable possède un noyau calculable en temps polynomial et dont la taille est majorée par f(k) pour une fonction gf'.

Tout problème FPT admet une réduction (en temps polynomial en ${\displaystyle n}$) à un noyau (a priori de taille exponentielle en ${\displaystyle k}$).

Il en résulte que la classe de complexité FPT correspond exactement à la classe de problèmes paramétrés dont les noyaux sont majorés par une fonction du paramètre. Même pour les problèmes qui ne sont pas fixed parameter tractable, pour lesquels une taille du noyau relativement petite ne peut pas être garantie, une réduction au noyau préalable à chaque appel récursif peut s'avérer avoir une utilité en pratique, parce qu'ils peuvent apporter des améliorations considérables pour les temps de calculs.

La kernelisation, comme la complexité paramétrée, est un domaine de recherche en pleine activité : pour 2016, il y a 38 articles ou communications à des colloques recensés dans la base DBLP^[3] sous le vocable « kernelisation ».

Notes et références[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

• Rodney G. Downey et Michael R. Fellows, Parameterized Complexity, Springer, 1999 (ISBN 0-387-94883-X, DOI 10.1007/978-1-4612-0515-9, MR 1656112).
• Rodney G. Downey et Michael R. Fellows, Fundamentals of Parameterized Complexity, Springer, 2013, xxx+763 (ISBN 978-1-4471-5558-4 et 978-1-4471-5559-1, DOI 10.1007/978-1-4471-5559-1, MR 3154461, présentation en ligne).
• Jörg Flum et Martin Grohe, Parameterized Complexity Theory, Springer, 2006, xiii+495 (ISBN 978-3-540-29952-3, présentation en ligne).
• Rolf Niedermeier, Invitation to Fixed-Parameter Algorithms, Oxford University Press (n^o 31), 2006, xi+300 (ISBN 0-19-856607-7, SUDOC 112132154).
• Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Daniel Marx, Marcin Pilipczuk, Michał Pilipczuk et Saket Saurabh, Parametrized Algorithms, Springer, 2015, xvii+613 (ISBN 978-3-319-21274-6 et 978-3-319-21275-3, DOI 10.1007/978-3-319-21275-3).

• Hans L. Bodlaender, Rod G. Downey, Michael R. Fellows et Danny Hermelin, « On problems without polynomial kernels », Journal of Computer and System Sciences, vol. 75, n^o 8,‎ 2009, p. 423–434 (DOI 10.1016/j.jcss.2009.04.001).
• Michael Lampis, « A kernel of order 2k − c log k for vertex cover », Information Processing Letters, vol. 111, n^os 23–24,‎ 2011, p. 1089–1091 (DOI 10.1016/j.ipl.2011.09.003).
• Stéphan Thomassé, « A 4k² kernel for feedback vertex set », ACM Transactions on Algorithms, vol. 6, n^o 2,‎ 2010 (DOI 10.1145/1721837.1721848).

Article lié[modifier | modifier le code]

• Chaîne la plus proche

Liens externes[modifier | modifier le code]

• Frédéric Havet, Christophe Paul, « Introduction aux algorithmes FPT ».
• Un wiki sur la complexité paramétrée (en).
• Christophe Paul, « Complexité et algorithmes paramétrés (1) » et « Complexité et algorithmes paramétrés (2) », Perpignan, avril 2013, École des jeunes chercheurs.

• Portail de l'informatique théorique