Verwenden von Farboptimierung oder Farbentscheidung zur Lösung der Farbsuche

Question

Wie kann man das zeigen? Malsuche kann gelöst werden, indem eine polynomiale Anzahl von Aufrufen der Lösung für durchgeführt wird Farboptimierung oder Farbentscheidung? (Farbsuche ist der Algorithmus zum Färben der Scheitelpunkte eines Diagramms, sodass benachbarte Scheitelpunkte eine andere Farbe haben.)

Ich war mir nicht sicher, wie ich das Problem lösen sollte, aber hier ist, was ich versucht habe (ich habe mich für Folgendes entschieden: Farboptimierung):

Farbsuche kann durch einen Anruf gelöst werden Farboptimierung und den Wert $ m $ zu finden, der die Anzahl der benötigten Farben ist, damit keine zwei benachbarten Eckpunkte die gleiche Farbe haben.Sobald $m$ gefunden wurde, Malsuche Kann die Scheitelpunkte des Diagramms färben, indem sie für jeden Scheitelpunkt durch die verschiedenen Farben $ M $ durchdrehen.

Bin ich auf dem richtigen Weg?

Answer 1

Bei einem gegebenen Graphen $G$ wollen wir zwei Dinge tun:

1. Finden Sie das kleinste $k$, so dass $G$ $k$-färbbar ist,
2. Finden Sie bei gegebenem $k$ eine Färbung von $G$ mit $k$-Farben.

Wenn wir ein Orakel für die Entscheidungsversion des Farbproblems haben, können wir beides tun.

Im ersten Teil können wir eine Suche durchführen, um das optimale $k$ zu finden.Sogar der naive Ansatz hier ist in Ordnung, wir können einfach sequentiell fragen, ob $G$ für $k=1,2,\ldots,n$ $k$-färbbar ist.Dann machen wir höchstens $n$ Aufrufe an das Orakel.Natürlich können wir eine binäre Suche durchführen und diese auf $\log n$ Aufrufe reduzieren.(Beachten Sie, dass wir auf diese Weise auch die Optimierungsversion mit der Entscheidungsversion lösen.)

Nachdem wir dann herausgefunden haben, welches $k$ optimal ist, können wir mithilfe des Entscheidungsorakels eine $k$-Färbung von $G$ finden.Der einzige Nachteil besteht darin, dass das Orakel keine Teilfärbungen akzeptiert. Daher benötigen wir eine Möglichkeit, im Diagramm zu kodieren, dass ein bestimmter Scheitelpunkt in einer bestimmten Farbe gefärbt wurde.

Dazu verwenden wir tatsächlich das Orakel auf einem Hilfsgraphen, den wir $G^{+}$ nennen werden, also $G$ plus ein $K_{k}$ mit einigen zusätzlichen Kanten.Natürlich benötigt $K_{k}$ genau $k$ Farben, daher können wir seine Scheitelpunkte verwenden, um anzugeben, welche Farben für einen Scheitelpunkt verfügbar sind.Die Eckpunkte $\{k_{1},\ldots,k_{k}\}$ des $K_{k}$ entsprechen den Farben $\{c_{1},\ldots,c_{k}\} $.Dann geben wir an, dass ein Scheitelpunkt $v$ in $G$ ist kann nicht mit der Farbe $c_{i}$ gefärbt werden, indem es an $k_{i}$ angrenzt.Wenn wir außerdem einen Scheitelpunkt mit der Farbe $c_{j}$ färben, machen wir ihn angrenzend an jeden $k_{i}$ mit $i eq j$ (und nicht neben $k_{j}$).

Dann machen wir wiederholt Folgendes:

1. Wählen Sie einen 'ungefärbten' Scheitelpunkt $v \in V(G)$.
2. Für jeden Scheitelpunkt $u \in N(v)$ gibt es, wenn $u$ gefärbt wurde, ein $k_{i}$ mit $uk_{i} otin E(G)$.Addiere die Kante $vk_{i}$ zu $E$.
3. Für die verbleibenden Eckpunkte $k_{j}$, so dass $vk_{j}$ noch nicht in $E$ ist, addieren wir alle andere Kanten zwischen $v$ und $K_{k}$ und fragen Sie das Orakel, ob der neue Graph $k$-färbbar ist.Wenn dies der Fall ist, behalten wir diesen Graphen bei und fahren mit dem nächsten Scheitelpunkt fort. Wenn die Antwort Nein lautet, machen wir Schritt 3 rückgängig und versuchen es mit dem nächsten $k_{j}$.

Beachten Sie, dass, da $G$ $k$-färbbar ist, es einige $k_{j}$ gibt, mit denen Schritt drei funktionieren wird.Wenn wir dann jeden Scheitelpunkt verarbeitet haben, ist jeder Scheitelpunkt in $G$ nicht neben genau einem Scheitelpunkt im $K_{k}$ gibt dies an, mit welcher Farbe der Scheitelpunkt gefärbt werden kann, um die Färbung zu erhalten.Aus Schritt 2 sehen wir, dass dies nicht die gleiche Farbe wie einer seiner Nachbarn haben kann.

Im dritten Schritt führen wir höchstens $k$ Aufrufe an das Orakel durch, und zwar für jeden Scheitelpunkt in $G$, sodass wir insgesamt höchstens $(k+1)n$ Aufrufe an das Orakel tätigen (einschließlich der Suche). für $k$).