Voir la source de Kernelisation


En [[informatique théorique]], et notamment en [[théorie de la complexité (informatique théorique)|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 graphe]]s
Dans une instance du problème de ''[[coloration de graphe]]'' avec ''q'' couleurs, on peut successivement enlever les [[sommet (théorie des graphes)|sommets]] ''x'' dont le [[degré (théorie des graphes)|degré]] est inférieur à ''q'' puisque, dans une coloration en ''q'' couleurs du reste du graphe, le [[voisinage (théorie des graphes)|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 [[Lexique de la théorie des graphes#A|arêtes]] incidentes à ''x'' doivent être couvertes, et si ''x'' ne fait pas partie de la couverture, tous les sommets de son [[voisinage (théorie des graphes)|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 [[problème de la clique|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 {{harvsp |Downey|Fellows|1999}}, un ''problème paramétré'' est une partie <math>L\subseteq\Sigma^*\times\N</math> qui décrit un [[problème de décision]].

Une '''kernelisation''' pour un problème paramétré <math>L</math> est un algorithme qui prend une instance <math>(X,k)</math> et la transforme, en temps polynomial en la taille ''n'' de <math>X</math> et de la valeur <math>k</math> en une instance  <math>(X',k')</math> avec les propriétés suivantes : 
* <math>(X,k)</math> est dans  <math>L</math> si et seulement <math>(X',k')</math> est dans <math>L</math>,
* la taille de <math>X'</math> est majoré par une fonction calculable <math>f</math> en <math>k</math>,
* <math>k'</math> est majoré par une fonction en <math>k</math> indépendante de <math>n</math>.
Le résultat <math>(X',k')</math> de la kernelisation est appelé le '''noyau'''. La taille de <math>X'</math> 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 <math>k'=k^{O(1)}</math>, et un ''noyau linéaire'' si <math>k'=O(k)</math>. 
Si on trouve un tel algorithme, alors on sait résoudre le problème de départ en temps <math>h(f(k)) + n^{O(1)}</math>, où <math>h</math> est le coût d’un algorithme de résolution du problème non paramétré et où le terme <math>n^{O(1)}</math> correspond au coût polynomial de la réduction<ref name="Schaeffer">{{Lien web
|langue=
|url=http://www.enseignement.polytechnique.fr/informatique/INF550/Cours1011/INF550-2010-8-print.pdf
|titre=  Complexité paramétrique
|série= Cours d'informatique INF550
|auteur= Gilles Schaeffer
|année= 2010
|éditeur= École polytechnique
|consulté le=19 novembre 2016
|id=
}}.</ref>.

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

Une '''kernelisation''' pour un problème paramétré <math>L</math> est un algorithme qui prend une instance <math>X</math> avec paramètre <math>k</math>  et la transforme, en temps polynomial en une instance <math>Y</math> avec les propriétés suivantes : 
* <math>X</math> est dans <math>L</math> si et seulement si <math>Y</math> est dans  <math>L</math> et
* la taille de <math>Y</math> est majorée par une fonction calculable <math>f</math> en <math>k</math>.
Dans cette formulation, la borne sur la taille de <math>Y</math> implique que le paramètre de <math>Y</math> est aussi majoré par une fonction en <math>k</math>.

La fonction <math>f</math> est fréquemment appelée la taille du noyau. Si <math>f(k)=k^{O(1)}</math>, on dit que  <math>L</math> possède un ''noyau polynomial''. De même, si <math>f={O(k)}</math>, 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 [[Ensemble récursif|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|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.<br>
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é <math>k</math> qui sont nécessairement dans l'ensemble ouvrant. Le graphe restant n’a que des sommets de degré <math>\le k</math>. Il a donc <math>\le k^2</math> arêtes, sinon il ne peut pas être couvert par <math>k</math> sommets de degré <math>\le k</math>. Il reste donc au plus <math>2k^2</math> sommets non isolés : on a extrait un noyau de taille <math>O(k^2)</math> en temps <math>O(n + m)</math>. Avec la stratégie des arêtes on obtient un algorithme en <math>O(n + m + 2^kk^2)</math><ref name="Schaeffer"/>. Un algorithme ''brute-force'' opère en temps <math>O(n + m + 2^{2k^2})</math> 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 <math>4k^2</math> sommets  et <math>O(k^2)</math> arêtes<ref name="tms10">{{harvsp|Thomassé|2010}}</ref>.

== FPT et kernelisation ==
{{loupe|complexité paramétrée}}
Un ''problème paramétré'' est un langage formel <math>L\subseteq\Sigma^*\times \N</math>, où <math>\Sigma</math> est un alphabet fini ; la deuxième composante <math>k</math> d'une instance <math>(X,k) \in \Sigma^*\times \N</math> est appelé son ''paramètre''. Un problème <math>L\subseteq\Sigma^*\times \N</math> est  ''fixed-parameter-tractable'' s'il admet un algorithme qui, à paramètre fixé, décide d'une instance <math> (X,k)</math> de <math>L</math>  en temps  <math>f(k)\cdot n^{O(1)}</math>, 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 [[Complexité paramétrée#Classe FPT|''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  <math>n^{O(1)}+h(f(k))</math>.

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 <math>n</math>) à un noyau (a priori de taille exponentielle en <math>k</math>).

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]]<ref>[http://dblp.uni-trier.de/search?q=kernelization%20year%3A2016%3A ''Kernelization''] sur [[DBLP]].</ref> sous le vocable « kernelisation ».

== Notes et références ==
{{Références}}
{{Traduction/Référence|en|Kernelization|700848692|type=note}}
== Bibliographie ==
<!-- Livres -->
*{{Ouvrage
 | prénom1=Rodney G.
 | nom1=Downey
 | lien auteur1=Rod Downey
 | prénom2=Michael R.
 | nom2=Fellows
 | lien auteur2=Michael Fellows
 | titre=Parameterized Complexity
 | éditeur=Springer
 | série=Monographs in Computer Science
 | année=1999
 | isbn=0-387-94883-X
 | doi=10.1007/978-1-4612-0515-9
 | math reviews=1656112
}}.
*{{Ouvrage
 | prénom1=Rodney G.
 | nom1=Downey
 | prénom2=Michael R.
 | nom2=Fellows
 | titre=Fundamentals of Parameterized Complexity
 | éditeur=Springer
 | année=2013
 | pages totales=xxx+763
 | isbn=978-1-4471-5558-4
 | isbn2=978-1-4471-5559-1
 | doi=10.1007/978-1-4471-5559-1
 | math reviews=3154461
 | présentation en ligne=https://www.springer.com/computer/theoretical+computer+science/book/978-1-4471-5558-4
}}.
* {{Ouvrage
 | prénom1=Jörg
 | nom1=Flum
 | prénom2=Martin
 | nom2=Grohe
 | titre=Parameterized Complexity Theory
 | éditeur=Springer
 | année=2006
 | pages totales=xiii+495
 | isbn=978-3-540-29952-3
 | présentation en ligne=https://www.springer.com/east/home/generic/search/results?SGWID=5-40109-22-141358322-0
}}.
* {{Ouvrage
| prénom1=Rolf
| nom1=Niedermeier
| titre=Invitation to Fixed-Parameter Algorithms
| éditeur=[[Oxford University Press]]
| série=Oxford Lecture Series in Mathematics and its Applications
| numéro dans collection=31
| année=2006
| pages totales=xi+300
| isbn=0-19-856607-7
| sudoc=112132154
}}.
* {{Ouvrage
| auteur1       = Marek Cygan
| auteur2       = Fedor V. Fomin
| auteur3       = Łukasz Kowalik
| auteur4       = Daniel Lokshtanov
| auteur5       = Daniel Marx
| auteur6       = Marcin Pilipczuk
| auteur7       = Michał Pilipczuk
| auteur8       = Saket Saurabh
| titre         = Parametrized Algorithms
| éditeur       = Springer
| année         = 2015
| pages totales = xvii+613
| isbn          = 978-3-319-21274-6
| isbn2         = 978-3-319-21275-3
| doi           = 10.1007/978-3-319-21275-3
}}.

<!-- Articles -->
* {{article
 | nom1 = Bodlaender| prénom1 = Hans L. | lien auteur1 = Hans L. Bodlaender
 | nom2 = Downey| prénom2 = Rod G. | lien auteur2 = Rod Downey
 | nom3 = Fellows| prénom3 = Michael R. | lien auteur3 = Michael Fellows
 | nom4 = Hermelin| prénom4 = Danny
 | journal = Journal of Computer and System Sciences
 | volume= 75 | numéro = 8
 | pages = 423–434
 | année = 2009
 | doi = 10.1016/j.jcss.2009.04.001
 | titre = On problems without polynomial kernels}}.
* {{article
 | nom1 = Lampis| prénom1 = Michael
 | journal = Information Processing Letters
 | volume = 111
 | numéro = 23–24
 | pages = 1089–1091
 | année = 2011
 | doi = 10.1016/j.ipl.2011.09.003
 | titre = A kernel of order 2''k''&nbsp;&minus;&nbsp;''c''&nbsp;log&nbsp;''k'' for vertex cover}}.
* {{article
 | nom1 = Thomassé| prénom1 = Stéphan
 | journal = [[ACM Transactions on Algorithms]]
 | volume= 6 | numéro = 2
 | titre = A 4''k''<sup>2</sup> kernel for feedback vertex set
 | année = 2010
 | doi = 10.1145/1721837.1721848
}}.

== Article lié ==
* [[Chaîne la plus proche]]

== Liens externes ==
* Frédéric Havet, Christophe Paul, [https://www-sop.inria.fr/mascotte/seminaires/JCALM/FPT.pdf « Introduction aux algorithmes FPT »].
* Un [http://fpt.wikidot.com/ wiki sur la complexité paramétrée] {{en}}.
* Christophe Paul, [http://www.lirmm.fr/~paul/Talks/talk-13-EJC-1.pdf « Complexité et algorithmes paramétrés (1) »] et [http://www.lirmm.fr/~paul/Talks/talk-13-EJC-2.pdf « Complexité et algorithmes paramétrés (2) »], Perpignan, {{date-|avril 2013}}, ''École des jeunes chercheurs''.

{{Palette Théorie de la complexité}}
{{portail|informatique théorique}}
[[Catégorie:Méthode algorithmique]]
[[Catégorie:Théorie de la complexité des algorithmes]]