Worldlex Wiki La réduction du noyau est souvent obtenue en appliquant un ensemble de règles de réduction qui éliminent les parties de l'instance les plus faciles à traiter. En théorie de la complexité paramétrée , il est souvent possible de démontrer qu'un noyau dont la taille est bornée (en fonction d'un paramètre associé au problème) peut être trouvé en temps polynomial . Lorsque cela est possible, on obtient un algorithme à paramètre fixe dont le temps d'exécution est la somme de l'étape de réduction du noyau (en temps polynomial) et du temps de résolution du noyau (non polynomial mais borné par le paramètre). En effet, tout problème pouvant être résolu par un algorithme à paramètre fixe peut être résolu par un algorithme de réduction du noyau de ce type. Ceci est également vrai pour la réduction du noyau approximative .
problème de couverture de sommets par S. Buss. Dans ce problème, l'entrée est un graphe non orienté et un nombre . La sortie est un ensemble d'au plus sommets contenant l'extrémité de chaque arête du graphe, si un tel ensemble existe, ou une exception d'échec dans le cas contraire. Ce problème est NP-difficile . Cependant, les règles de réduction suivantes peuvent être utilisées pour le kerneliser :
0 
0 Définition
Dans la littérature, il n'existe pas de consensus clair sur la manière dont la définition formelle de la nucléation devrait être établie, et il existe des différences subtiles dans l'utilisation de cette expression.
Notation de Downey-Fellows
Dans la notation de 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 et en une instance telle que
- la taille de est bornée par une fonction calculable dans , et
Le résultat de la réduction à un noyau est appelé noyau. Dans ce contexte général, la taille de la chaîne fait simplement référence à sa longueur. Certains auteurs préfèrent utiliser le nombre de sommets ou le nombre d'arêtes comme mesure de taille dans le contexte des problèmes de graphes.
Notation Flum-Grohe
Dans la notation de
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 telle que
- la taille de est bornée par une fonction calculable dans .
Notez que dans cette notation, la borne sur la taille de implique que le paramètre de est également borné par une fonction dans .
Cette fonction est souvent appelée la taille du noyau. Si , on dit que admet un noyau polynomial. De même, pour , le problème admet un noyau linéaire.
La nucléosabilité et la tractabilité à paramètre fixe sont équivalentes
Un problème est traitable à paramètre fixe si et seulement s'il est noyautable et décidable .
Le fait qu'un problème à noyau et décidable soit traitable à paramètre fixe se vérifie d'après la définition ci-dessus : on appelle d'abord l'algorithme de noyautage, dont le temps d'exécution est O(n^c) pour une certaine valeur de c, afin de générer un noyau de taille n . Ce noyau est ensuite résolu par l'algorithme qui prouve que le problème est décidable. La durée totale de cette procédure est O(n^c) , où n est le temps d'exécution de l'algorithme utilisé pour résoudre les noyaux. Puisque n est calculable, par exemple en supposant que n est calculable et en testant toutes les entrées possibles de longueur n , cela implique que le problème est traitable à paramètre fixe.
L'autre direction, à savoir qu'un problème traitable à paramètre fixe est noyautable et décidable, est un peu plus complexe. Supposons que le problème soit non trivial, c'est-à-dire qu'il existe au moins une instance appartenant au langage, notée , et au moins une instance n'y appartenant pas, notée ; sinon, remplacer toute instance par la chaîne vide constitue une noyautable valide. Supposons également que le problème soit traitable à paramètre fixe, c'est-à-dire qu'il admette un algorithme s'exécutant en au plus étapes sur les instances , pour une certaine constante et une certaine fonction . Pour noyautiser une entrée, on exécute cet algorithme sur l'entrée donnée en au plus étapes. S'il se termine avec une réponse, on utilise cette réponse pour sélectionner soit ou comme noyau. Si, en revanche, il dépasse la limite du nombre d'étapes sans se terminer, alors on retourne lui-même comme noyau. Puisque n'est retourné comme noyau que pour les entrées avec , il s'ensuit que la taille du noyau ainsi produit est au plus . Cette limite de taille est calculable, par hypothèse de traitabilité à paramètre fixe selon laquelle est calculable.
|x|^{c+1 Plus d'exemples
- Paramétrisation de la couverture de sommets par sa taille : Le problème de la couverture de sommets admet des noyaux comportant au plus sommets et arêtes. De plus, pour tout , la couverture de sommets n'admet pas de noyaux avec arêtes sauf si . Les problèmes de couverture de sommets dans les hypergraphes -uniformes admettent des noyaux avec arêtes grâce au lemme du tournesol , et n'admettent pas de noyaux de taille sauf si .
- Ensemble de sommets de rétroaction paramétré par sa taille : Le problème de l’ensemble de sommets de rétroaction comporte des noyaux avec des sommets et des arêtes. De plus, il ne comporte pas de noyaux avec des arêtes, sauf si …
- Le problème -chemin consiste à déterminer si un graphe donné possède un chemin de longueur au moins . Ce problème admet des noyaux de taille exponentielle en , et n’admet pas de noyaux de taille polynomiale en sauf si .
- Problèmes bidimensionnels : De nombreuses versions paramétrées de problèmes bidimensionnels ont des noyaux linéaires sur des graphes planaires, et plus généralement sur des graphes excluant un graphe fixe comme mineur .
0 Noyauisation pour les paramétrisations structurelles
Bien que le paramètre des exemples précédents soit choisi comme la taille de la solution souhaitée, cela n'est pas obligatoire. Il est également possible de choisir une mesure de complexité structurelle de l'entrée comme valeur du paramètre, ce qui conduit à ce que l'on appelle les paramétrisations structurelles. Cette approche est fructueuse pour les instances dont la taille de la solution est importante, mais pour lesquelles une autre mesure de complexité est bornée. Par exemple, le nombre de sommets de rétroaction d'un graphe non orienté est défini comme la cardinalité minimale d'un ensemble de sommets dont la suppression rend le graphe acyclique. Le problème de couverture de sommets paramétré par le nombre de sommets de rétroaction du graphe d'entrée admet une kernelisation polynomiale : Il existe un algorithme polynomial qui, étant donné un graphe dont le nombre de sommets de rétroaction est , produit un graphe à sommets tel qu'une couverture minimale de sommets dans puisse être transformée en une couverture minimale de sommets pour en temps polynomial. L'algorithme de kernelisation garantit donc que les instances avec un petit nombre de sommets de rétroaction sont réduites à de petites instances.