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.

ExemplesModifier

Avant de donner une définition formelles, 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 xdont 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 formelleModifier

Deux formulations proches ont été proposées :

Formulation de Downey et FellowsModifier

Pour Downey et Fellows 1999, un problème paramétré est une partie   qui décrit un problème de décision.

Une kernelisation pour un problème paramétré   est un algorithme qui prend une instance   et la transforme, en temps polynomial en la taille n de   et de la valeur   en une instance   avec les propriétés suivantes :

  •   est dans   si et seulement   est dans  ,
  • la taille de   est majoré par une fonction calculable   en  ,
  •   est majoré par une fonction en   indépendante de  .

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

Formulation de Flum et GroheModifier

Pour Flum et Grohe 2006, p. 4, un problème paramétré est composé d'un problème de décision   et d'une fonction  , la paramétrisation. Le paramètre d'une instance   est le nombre  .

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

  •   est dans   si et seulement si   est dans   et
  • la taille de   est majorée par une fonction calculable   en  .

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

La fonction   est fréquemment appelée la taille du noyau. Si  , on dit que   possède un noyau polynomial. De même, si  , le problème possède un noyau linéaire.

RemarqueModifier

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

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

FPT et kernelisationModifier

Un problème paramétré est un langage formel  , où   est un alphabet fini ; la deuxième composante   d'une instance   est appelé son paramètre. Un problème   est fixed-parameter-tractable s'il admet un algorithme qui, à paramètre fixé, décide d'une instance   of   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 The class of fixed-parameter tractable 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  .

Réciproquement, on peut démontrer que toute instance (X,k) d'un problème fixed-parameter-tractable possède une 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  ) à un noyau (a priori de taille exponentielle en  ).

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

  1. a et b Gilles Schaeffer, « Complexité paramétrique », Cours d'informatique INF550, École polytechnique, (consulté le 19 novembre 2016).
  2. Thomassé 2010
  3. Kernelization sur DBLP.
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Kernelization » (voir la liste des auteurs).

BibliographieModifier

Article liéModifier

Liens externesModifier