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

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

Deux formulations proches ont été proposées :

Formulation de Downey et Fellows

Pour Modèle:Harvsp, un problème paramétré est une partie $L\subseteq {\mathrm{\Sigma }}^{*}\times \mathbb{N}$ qui décrit un problème de décision.

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

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

Le résultat $(X^{\prime },k^{\prime })$ de la kernelisation est appelé le noyau. La taille de $X^{\prime }$ 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 $k^{\prime }=k^{O(1)}$, et un noyau linéaire si $k^{\prime }=O(k)$. Si on trouve un tel algorithme, alors on sait résoudre le problème de départ en temps $h(f(k))+n^{O(1)}$, où $h$ est le coût d’un algorithme de résolution du problème non paramétré et où le terme $n^{O(1)}$ correspond au coût polynomial de la réduction.

Formulation de Flum et Grohe

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

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

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

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

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

Remarque

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)

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é $k$ qui sont nécessairement dans l'ensemble ouvrant. Le graphe restant n’a que des sommets de degré $\le k$. Il a donc $\le k^2$ arêtes, sinon il ne peut pas être couvert par $k$ sommets de degré $\le k$. Il reste donc au plus $2k^2$ sommets non isolés : on a extrait un noyau de taille $O(k^2)$ en temps $O(n+m)$. Avec la stratégie des arêtes on obtient un algorithme en $O(n+m+2^k{k}^2)$. Un algorithme brute-force opère en temps $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 $4k^2$ sommets et $O(k^2)$ arêtes.

FPT et kernelisation

Modèle:Loupe Un problème paramétré est un langage formel $L\subseteq {\mathrm{\Sigma }}^{*}\times \mathbb{N}$, où $\mathrm{\Sigma }$ est un alphabet fini ; la deuxième composante $k$ d'une instance $(X,k)\in {\mathrm{\Sigma }}^{*}\times \mathbb{N}$ est appelé son paramètre. Un problème $L\subseteq {\mathrm{\Sigma }}^{*}\times \mathbb{N}$ est fixed-parameter-tractable s'il admet un algorithme qui, à paramètre fixé, décide d'une instance $(X,k)$ de $L$ en temps $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 $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 $n$) à un noyau (a priori de taille exponentielle en $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 sous le vocable « kernelisation ».

Bibliographie

• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.
• Modèle:Ouvrage.

• Modèle:Article.
• Modèle:Article.
• Modèle:Article.

Article lié

• Chaîne la plus proche

Liens externes

• Frédéric Havet, Christophe Paul, « Introduction aux algorithmes FPT ».
• Un wiki sur la complexité paramétrée Modèle:En.
• Christophe Paul, « Complexité et algorithmes paramétrés (1) » et « Complexité et algorithmes paramétrés (2) », Perpignan, Modèle:Date-, École des jeunes chercheurs.