(Méta)-noyaux constructifs et linéaires dans les graphes peu denses

Consid´erons un fruit, ´epluchons-le et jetons la peau, elle ne nous sert pas ; retirons-en la chair, nous pouvons la jeter aussi, elle ne nous est pas utile ; car tout ce dont nous avons besoin c’est du noyau, en plantant celuici nous obtiendrons un arbre lequel produira de nouveaux fruits, entiers. Cela est possible parce que le noyau `a lui seul contient toute l’information g´en´etique pour produire un arbre et des fruits. Le proc´ed´e algorithmique appel´e extraction de noyau est bas´e sur la mˆeme id´ee, il s’agit d’un calcul pr´eliminaire visant `a r´eduire les donn´ees d’un probl`eme `a leur plus simple expression tout en conservant suffisamment d’information pour reconstituer une solution.

Pour mieux comprendre la notion algorithmique de noyau, il convient d’abord de faire quelques rappels sur l’algorithmie.

Prologue

Un algorithme est une s´equence d’instructions qui a pour but de r´epondre `a un probl`eme ou d’obtenir un r´esultat. L’algorithmie est la science qui s’int´eresse `a la conception des algorithmes et `a l’´etude de leur complexit´e, c’est-`a-dire au temps qui leur est n´ecessaire pour r´epondre au probl`eme. Dans cette section introductive nous tenterons de donner une intuition de ces trois notions : algorithme, probl`eme, et complexit´e.

Algorithme
Un algorithme est, comme nous l’avons dit, une s´equence d’instructions qui vise `a  esoudre un probl`eme particulier. En d’autres termes, c’est une recette qui sp´ecifie quels calculs effectuer pour r´epondre `a un probl`eme. Un algorithme aspire `a plus de g´en´eralit´e qu’un calcul, en effet il utilise une entr´ee (parfois appel´ee donn´ee ou argument) qui est une inconnue pour le concepteur de l’algorithme et qui sera ensuite instanci´ee par l’utilisateur. Il peut ˆetre mis en parall`ele avec la notion mathematique de fonction, la variable d’une fonction correspondant `a l’entr´ee d’un algorithme. Cependant alors que la fonction est une sorte de boite noire qui ´etant donn´ee une certaine valeur de la variable renvoie un r´esultat, l’algorithme ce doit d’indiquer comment, pour une certaine instanciation de l’entr´ee, il est possible de calculer la r´eponse. Dans une certaine mesure, un informaticien pourrait consid´erer une fonction (calculable) comme la classe d’´equivalence de tous les algorithmes qui, pour une mˆeme entr´ee, renvoient la mˆeme r´eponse ; possiblement par des calculs diff´erents (et donc plus ou moins efficaces). Par exemple un polynˆome peut s’´ecrire indiff´eremment sous sa forme d´evelopp´ee P(X) = X² + 2X + 1 ou sous sa forme factoris´ee P(X) = (X + 1)² . Il s’agira toujours de la mˆeme fonction, pourtant du point de vue du calcul, il s’agit de deux s´equences d’op´erations bien distinctes.

Le plus c´el`ebre des algorithmes est l’anthyph´er`ese d’Euclide, qui calcule le plus grand commun diviseur de deux entiers. Cependant, l’algorithmie ne devient une science `a part enti`ere qu’au XXe si`ecle : le 10e des 23 probl`emes de Hilbert ´etait de trouver une m´ethode pour d´eterminer l’existence de solutions `a une ´equation diophantienne. Une telle m´ethode (c’est-`a-dire, un tel algorithme) n’existe pas ; pour en obtenir la preuve, il a fallu d´efinir rigoureusement ce qu’est une m´ethode. En effet, il est toujours plus facile d’exhiber un exemple d’une chose, que de demontrer l’inexistence de cette chose ; pour dire qu’une chose n’existe pas, il faut d’abord d´efinir quelle forme elle peut prendre. En bref, pour r´epondre au probl`eme de Hilbert, il a fallu d´efricher  une nouvelle branche des math´ematiques. Il existe donc des mod`eles de calcul, tels que la machine `a computer de Turing ou le λ calcul de Church, qui formalisent la notion d’algorithme. Cependant, le sujet de notre th`ese ne n´ecessite pas de rentrer dans un tel niveau de technicit´e. Nous nous satisferons tr`es largement de la d´efinition informelle : un algorithme est une sequence d’instructions d´ependant d’une entr´ee. Le corps d’un algorithme est compos´e d’instructions ´el´ementaires (comme l’addition si l’entr´ee est un nombre, ou l’ajout de sommet si c’est un graphe) et d’instructions particuli`eres qui permettent d’automatiser le calcul : l’instruction conditionnelle (si une condition est v´erifi´ee alors faire l’instruction), la boucle conditionnelle (tant que une condition n’est pas verifi´ee faire l’instruction `a r´ep´eter), la boucle index´ee (pour chaque ´el´ement d’un ensemble faire l’instruction `a r´ep´eter), l’appel de fonction (pour l’appel recursif, par exemple). Ces instructions correspondent aux expressions utilis´ees dans les langages de programmation. Par hypoth`ese, les instructions ´el´ementaires peuvent ˆetre ex´ecut´ees en une unit´e de temps ; elles sont ensuite r´ep´et´ees un certain nombre de fois grˆace aux boucles. Se pose alors la question du temps d’execution d’un algorithme.

(M´eta)-noyau
Consid´erons plus en d´etail l’algorithmie param´etr´ee. Cette branche part du postulat que la taille de l’instance n’est pas toujours le bon indicateur pour mesurer la complexit´e du probl`eme. Elle consid`ere donc une seconde mesure de l’instance, appel´ee param`etre, qui est la cause de l’explosion combinatoire (c’est-`a-dire de la complexit´e exponentielle). La complexit´e d’un probl`eme est analys´ee en fonction de la taille et du param`etre. Si la taille de l’instance n’est pas cause de complexit´e, autrement dit, si un accroissement de l’instance n’implique pas une croissance de la difficult´e, c’est bien que l’instance contient de l’information superflue (non necessaire `a la r´esolution du probl`eme). Le principe de l’extraction de noyaux consiste `a retirer cette information inutile. Cette id´ee existait d´ej`a dans le monde des heuristiques, il s’agissait alors de faire un pr´e-calcul facile, afin de simplifier les donn´ees du probl`eme, avant de s’attaquer `a la partie difficile. L’extraction de noyaux est tr`es exactement un pr´e-calcul, mais avec deux garanties th´eoriques : celle que l’ensemble des solutions reste identique, et celle que l’instance a ´et´e suffisamment ´elagu´ee, compress´ee. Ainsi un noyau fournit un algorithme parametre : le pr´e-calcul se fait en temps polynomial en fonction de la taille de l’instance, puis la r´esolution du probl`eme (de complexit´e exponentielle) ne d´epend que du param`etre car l’instance a ´et´e suffisamment r´eduite.

De plus, comme l’annonce son titre, cette th`ese s’int´eresse `a des metaalgorithmes d’extraction de noyau. Le pr´efixe m´eta- souligne une ´etape suppl´ementaire dans la g´en´eralisation. Nous l’avons vu, un probl`eme g´en´eralise une question en laissant une partie, l’instance, inconnue. Pour r´esoudre un probl`eme il faut utiliser un algorithme qui g´en´eralise le calcul, y laissant une variable, l’entr´ee, indeterminee. L’objectif de cela est de proposer une m´ethode qui permet d’automatiser une famille de calculs similaires. De mˆeme que, dans un probl`eme, l’instance est une inconnue, une variable ; de mˆeme nous pourrions, pour plus de gen´eralit´e encore, laisser ind´etermin´ee la question. La description du probl`eme ferait alors partie de l’entr´ee de l’algorithme. Bien sˆur nous ne pourrions pr´etendre faire de la question une inconnue totale. Si nous n’imposons pas certaines contraintes sur le probl`eme de l’entr´ee, notre algorithme devient une sorte de machine universelle de Turing. Et nous nous heurterions `a la th´eorie de la calculabilit´e qui dit impossible l’analyse de complexit´e sur une telle machine. Mais nous pourrions vouloir consid´erer en un seul bloc tous les probl`emes dont la question peut ˆetre exprim´ee sous une certaine forme. Un m´eta-probl`eme est une famille de probl`emes ayant une description commune. Un m´eta-algorithme est un algorithme qui, en une fois, d´ecrit la m´ethode pour r´esoudre toute une famille de probl`eme.

Un m´eta-noyau est donc un algorithme qui, ´etant donn´e un probl`eme et une instance, est capable de r´eduire l’instance, de sorte que instance initiale et instance r´eduite soient ´equivalentes par rapport au probl`eme donn´e. Une autre approche consiste `a voir un m´eta-noyau comme un algorithme qui, ´etant donn´ee la description d’un probl`eme, renvoie une extraction de noyau adapt´e `a ce probl`eme.