Le graphique 3-colorabilité est auto-réducteur

Question

Je suis intéressé par autoréductibilité du graphique problème 3 Coloralibity.

Définition du problème Graphique 3 Coloralibity.

Étant donné un graphe non orienté $ G $ fait il existe une façon de colorer les nœuds rouges, si vert et bleu qu'aucun des noeuds adjacents ont la même couleur?

Définition de autoréductibilité.

Un langage $ L $ est auto-réducteur si un oracle machine de Turing TM existe $ T $ tel que $ L = L (T ^ L) $ et pour tout $ d'entrée x $ de $ de longueur n, $ T ^ l (x) $ interroge l'oracle des mots de longueur au plus $ n-1 $.

Je voudrais montrer de manière très stricte et formelle que le graphique 3-colorabilité est auto-réductible.

Preuve de autoréductibilité de SAT peut être utilisé comme exemple ( auto réductibilité de SAT ).

À mon avis, l'idée générale de la preuve de autoréductibilité du graphique 3-colorabilité est différente de la preuve de SAT autoréductibilité dans quelques aspects.

• SAT a deux choix pour chaque littéral (vrai ou faux) et le graphique 3 a trois choix colorabilité (à savoir, rouge vert bleu).
• Choix de SAT littéral sont indépendants les uns des autres et les choix de couleurs de colorabilité Graphique 3 sont strictement dépendants, un nœud adjacent doit avoir la couleur différente, cette propriété pourrait potentiellement aider à faire moins d'itération parmi toutes les couleurs.

L'idée générale de la preuve .

Soit s On note $ c_ {v_i} $ la couleur du sommet $ v_i $, ce qui peut prendre l'une des valeurs suivantes (rouge, vert, bleu). Définir le graphique $ G « $ d'un donné graphique $ G $ en colorant l'arbitraire sommet $ v_0 $, assign $ c_ {v_0} $ à « rouge » et de mettre le graphique $ G » $ avec le sommet de couleur v_0 $ $ à l'entrée de l'oracle. Si Oracle répond 1, ce qui signifie que le graphe modifié est encore 3-colorable, enregistrez les affectations en cours et lanceront une nouvelle itération, avec les différents sommets v_1 $ $ choisi arbitrairement, sommet couleur v_1 $ $ selon les couleurs des sommets adjacents. Si les réponses oracle 0, ce qui signifie l'assignation précédente a rompu 3 colorabilité, choisir la couleur différente de l'ensemble des trois couleurs, mais toujours selon les couleurs de sommets adjacents.

La preuve précédente n'est pas mathématique solide, la question est de savoir comment l'améliorer et de le rendre plus formel et mathématique stricte. On dirait que je dois distinguer plus soigneusement les cas lorsque le nouveau sommet n'a pas de bords avec des sommets déjà colorés et lorsque le nouveau sommet est adjacent aux sommets déjà colorés.

En outre, je voudrais prouver que le graphique 3-colorabilité est vers le bas auto-réducteur.

Définition de la baisse de la langue auto réductible.

La langue $ A $ est dite auto-réducteur vers le bas s'il est possible de déterminer en temps polynomial si $ x \ in A $ en utilisant les résultats des requêtes les plus courtes.

L'idée semble être simple et intuitive: commencer par la coloration d'un sommet arbitraire, et à chaque ajout d'itération d'un sommet plus coloré et vérifier par oracle si le graphique est encore 3-colorable, sinon la coloration inverse précédente et vérifier une autre couleur.

Mais comment écrire la preuve d'une manière stricte et plus important de voir comment trouver un codage approprié d'un graphe.

En bref, je voudrais montrer que le graphique 3-colorabilité est auto-réducteur auto-réducteur et vers le bas de manière stricte et formelle.

J'appréciera partager avec nous vos pensées.

Mise à jour:

autoréductibilité vers le bas

autoréductibilité Vers le bas est appliqué à un problème de décision et d'Oracle, il répond le même problème de décision avec entrée plus courte, à la fin du processus d'auto-réduction à la baisse, nous devrions avoir les affectations de couleur.

Chaque 3 - colorable graphique $ G $ avec plus de trois sommets, a deux sommets $ x, y $ avec la même couleur. Apparemment, il n'y a que trois colors et plus de trois sommets donc un nombre de sommets non adjacents peuvent avoir la même couleur. Si nous fusionnons $ x $ et $ y $ avec la même couleur que le résultat que nous avons encore 3 - graphique colorable, juste parce que, si le graphique est 3 - colorable, alors il y a exister attribution droite de tous les sommets qui sont adjacents à $ x $ et $ y $ selon la même couleur de $ x, y $, alors en fusionnant $ x, y $ on n'a pas besoin de changer la couleur de tous les sommets, il suffit d'ajouter plus de bords entre les sommets déjà colorés correctement (Je sais que ce n'est pas la meilleure explication, je vais apprécier si quelqu'un pouvait l'expliquer mieux). A chaque itération, nous prenons deux sommets non adjacents $ x, y $ de graphique $ G $, $ x fusion $ et $ y $ et obtenez graphique $ G '$ qui est notre entrée plus courte à l'oracle. Oracle répond si elle est 3-colorable ou non. Maintenant, le problème est avant de $ G « $ sur l'entrée d'oracle je colorer le sommet fusionné et le test colorabilité de $ G » $, si ce n'est pas 3 coloriable changer la couleur, mais la façon de le mettre en œuvre correctement, je dois droit codant pour elle.

autoréductibilité

Tout d'abord, nous devons vérifier si un graphique donné $ G $ est 3-colorable du tout, donc mis sur l'entrée d'oracle et oracle répondra si elle est 3 - colorable, si oui alors commencer le processus. Tous les deux sommets peuvent avoir la non adjacents de même couleur dans le graphique 3-colorable. Le processus de autoréductibilité nous devrions courir en itérations, je pense que nous pouvons commencer à partir de $ G petit sous-graphe « $ d'un graphique donné $ G $ et à chaque itération ajouter un des sommets de $ G $ à $ G » $. En paralel, nous devons maintenir l'affectation des sommets déjà colorés. Malheureusement, je ne comprends toujours pas complètement l'idée. Apprécierait de l'aide et des conseils.

Answer 1

Vor mentionne dans son commentaire, votre réduction ne fonctionne pas, depuis le 3-colorabilité n'accepte pas les cessions partielles de couleurs. Le problème est encore plus profond, puisque le réglage de la couleur d'un seul sommet ne fait pas any progrès pour déterminer si le graphique est 3-colorable: en effet, le graphique est 3-colorable ssi il y a un 3 -coloration dans lequel vertex $ v $ est attribué couleur $ c $, pour tout v $, c $ vous choisissez.

Voici un indice sur la façon de résoudre votre exercice, deuxième partie. En tout 3 coloration d'un graphe $ G $ sur plus de trois sommets, il y a deux sommets $ x, y $ obtenir la même couleur (pourquoi?). Si nous fusionnons $ x $ et $ y $, le graphique résultant est encore 3-colorable (pourquoi?). Essayez d'utiliser cette idée de construire un algorithme d'auto-réduction de la baisse pour 3 colorabilité.

Edit: Et voici une indication sur la façon de résoudre l'exercice, première partie. Considérons deux sommets non connectés $ x, y $. S'il y a une coloration où ils obtiennent la même couleur puis $ G_ {xy} $ est 3-colorable (pourquoi?), Et une coloration de $ G $ peut être extrait d'une coloration de $ G_ {xy} $ (comment ?). Quand cela la fin du processus?