En utilisant l'optimisation de coloration ou d'une décision de coloration pour résoudre la recherche coloration

Question

Comment pouvez-vous montrer que recherche coloration peut être résolu en faisant un nombre polynomial d'appels à la solution pour l'optimisation coloration ou décision coloration ? ( Coloration recherche est l'algorithme pour colorer les sommets d'un graphe de telle sorte que les sommets adjacents ont une couleur différente.)

Je ne savais pas comment le résoudre, mais voici ce que je tentais (je choisi d'utiliser Optimisation coloration ):

recherche Coloriage peut être résolu en appelant l'optimisation coloration et trouver la valeur $ m $, ce qui est la quantité de couleurs nécessaires afin que deux sommets adjacents ont la même couleur. Une fois que $ m $ est trouvé, recherche coloration peut colorer les sommets du graphe en tournant à travers le $ m $ couleurs différentes pour chaque sommet.

Suis-je sur la bonne voie?

Answer 1

Soit un graphe $ G $, nous voulons faire deux choses:

1. Trouver le plus petit k $ $ tel que $ G $ est $ k $ -colourable,
2. Avec un tel $ k $, trouver une coloration de $ G $ avec $ k couleurs $.

Si nous avons un oracle pour la version de décision du problème de coloration, nous pouvons faire les deux.

Pour la première partie, nous pouvons effectuer une recherche pour trouver k optimale $ $. Même l'approche naïve ici est d'accord, nous pouvons simplement successivement demander si $ G $ est k $ $ -colourable pour $ k = 1,2, \ ldots, n $. Ensuite, nous faisons au plus $ n appels $ à l'oracle. Bien sûr, nous pouvons effectuer une recherche binaire et réduire cela à $ \ log n $ appels. (Notez que c'est aussi la façon dont nous résolvons la version d'optimisation avec la version de décision).

Ensuite, étant donné que nous avons travaillé ce qui est optimal, on peut trouver un k $ $ -colouring de $ G $ en utilisant l'oracle de décision $ $ k. La seule ride est que l'oracle ne prend pas partielle coloriages, donc nous avons besoin d'un moyen de codage dans le graphique qu'un sommet particulier a été colorée d'une couleur particulière.

Pour ce faire, nous utilisons en fait l'oracle sur un graphe auxilliaire, que nous appellerons G $ ^ {+} $, soit $ G $ plus un K_ $ {k} $ avec quelques arêtes supplémentaires. Bien sûr, le K_ $ {k} $ Besoins exactement $ k couleurs $, afin que nous puissions utiliser ses sommets pour indiquer quelles couleurs sont disponibles pour un sommet. Que les sommets $ \ {K_ {1}, \ ldots, K_ {k} \} $ du K_ $ {k} $ de correspondent aux couleurs $ \ {C_ {1}, \ ldots, C_ {k} \} $. Ensuite, nous allons indiquer qu'un $ sommet v $ en $ G $ ne peut pas être coloré par la couleur $ c_ {i} $ en le rendant à côté de $ K_ {i} $. En outre, si nous la couleur d'un sommet avec la couleur $ c_ {j} $, nous allons le faire à côté de tous $ K_ {i} $ avec $ i \ neq j $ (et pas à côté de $ K_ {j} $).

Ensuite, nous faisons à plusieurs reprises ce qui suit:

1. Choisissez un 'non coloré' vertex $ v \ en V (G) $.
2. Pour tout sommet u $ \ N (v) $, si $ u $ a été colorée, alors il est un $ K_ {i} $ tels que $ uk_ {i} \ Notin E (G) $. Ajouter le bord vk_ de $ {i} $ à $ E $.
3. Pour les autres sommets $ K_ {j} $ tel que $ vk_ {j} $ n'est pas encore $ E $, nous ajoutons tous les autres arêtes entre $ v $ et le K_ $ { k} $ et demander à l'oracle si le nouveau graphe est k $ $ -colourable. Dans ce cas, nous gardons ce graphique et passer au prochain sommet, si la réponse est non, nous défaisons l'étape 3 et essayer la prochaine K_ de $ {j} de $.

Notez que $ G $ est $ k $ -colourable, il y a quelques K_ $ {j} $ cette étape trois fonctionnera. Puis, quand nous avons traité tous les sommets, chaque sommet de $ G $ est pas adjacent à exactement un sommet dans la K_ $ {k} $, cela indique quelle couleur le sommet peut être coloré avec pour obtenir le coloration. A partir de l'étape 2, on voit que cela ne peut pas être la même couleur que l'un de ses voisins.

A la troisième étape, nous faisons au plus $ k appels $ à l'oracle, et nous le faisons pour chaque sommet de $ G $, donc au total que nous faisons au plus $ (k + 1) n appels $ à l'oracle ( y compris la recherche de $ k $).