Utilizzando l'ottimizzazione colorazione o di coloranti decisione per risolvere ricerca colorare

Question

Come si può dimostrare che Ricerca colorazione può essere risolto facendo un certo numero polinomiale di chiamate alla soluzione per colorazione ottimizzazione o decisione colorazione ? ( ricerca coloritura è l'algoritmo di colorare i vertici di un grafo tale che i vertici adiacenti hanno un altro colore.)

Non ero sicuro come risolverlo, ma qui è quello che ho tentato (ho scelto di utilizzare colorazione ottimizzazione ):

Ricerca Colorazione può essere risolto chiamando colorazione ottimizzazione e trovare il valore $ m $, che è la quantità di colori necessaria così che due vertici adiacenti hanno lo stesso colore. Una volta $ m $ viene trovato, Ricerca colorazione può colorare i vertici del grafo ruotando attraverso il $ m $ colori diversi per ogni vertice.

Sono sulla strada giusta?

Answer 1

Dato un grafo $ G $, vogliamo fare due cose:

1. Trova il più piccolo $ k $ tali che $ G $ è $ k $ -colourable,
2. Dato un tale $ k $, trovare una colorazione di $ G $ con $ k $ colori.

Se abbiamo un oracolo per la versione decisione del problema di colorazione, siamo in grado di fare entrambe le cose.

Per la prima parte siamo in grado di eseguire una ricerca per trovare l'ottimale $ k $. Anche l'approccio ingenuo qui va bene, possiamo solo chiederci se in sequenza $ G $ è $ k $ -colourable per $ k = 1,2, \ ldots, n $. Poi facciamo al massimo $ n $ chiamate verso l'oracolo. Naturalmente siamo in grado di effettuare una ricerca binaria e tagliare questo fino a $ \ log n $ chiamate. (Si noti che questo è anche il modo in cui risolvere la versione di ottimizzazione con la versione decisione).

Poi, dato che abbiamo lavorato fuori che cosa $ k $ è ottimale, possiamo trovare un $ k $ -colouring di $ G $ utilizzando l'oracolo decisione. L'unica antirughe è che l'oracolo non prende coloranti parziali, quindi abbiamo bisogno di un modo di codificare nel grafico che un particolare vertice è stata colorata con un colore particolare.

Per fare questo abbiamo effettivamente utilizzare l'oracolo su un grafico ausiliario, che chiameremo $ G ^ {+} $, che è di $ G $, più un $ K_ {k} $ con alcuni bordi supplementari. Naturalmente il $ K_ {k} $ esigenze esattamente $ k $ colori, in modo da poter utilizzare i suoi vertici per indicare quali colori sono disponibili per un vertice. Lasciate che i vertici $ \ {k_ {1}, \ ldots, k_ {k} \} $ del $ K_ {k} $ corrispondono ai colori $ \ {c_ {1}, \ ldots, c_ {k} \} $. Poi ci indicherà che un vertice $ v $ in $ G $ non può essere colorato con il colore $ c_ {i} $ rendendo adiacente a $ k_ {i} $. Inoltre, se coloriamo un vertice con il colore $ c_ {j} $ faremo adiacente al tutti $ k_ {i} $ con $ i \ neq j $ (e non adiacente a $ k_ {j} $).

Poi abbiamo ripetutamente fare quanto segue:

1. Scegli un 'incolore' vertice $ v \ in V (G) $.
2. Per ogni vertice u $ \ in N (v) $, se $ u $ è stato colorato, poi c'è un $ k_ {i} $ tale che $ uk_ {i} \ notin E (G) $. Aggiungere il bordo $ vk_ {i} $ a $ E $.
3. Per i restanti vertici $ k_ {j} $ tale che $ vk_ {j} $ non è ancora in $ E $, aggiungiamo tutti altro bordi tra $ v $ e $ K_ { k} $ e chiedere l'oracolo se il nuovo grafico è di $ k $ -colourable. Se lo è, continuiamo questo grafico e passa al vertice successivo, se la risposta è No, disfa il punto 3 e cerchiamo con il prossimo $ k_ {j} $.

Si noti che da $ G $ è $ k $ -colourable, v'è una certa $ k_ {j} $ che passo a tre lavorerà con. Poi quando abbiamo elaborato ogni vertice, ciascun vertice in $ G $ è non adiacente ad esattamente un vertice al $ K_ {k} $, ciò indica che il colore del vertice può essere colorato con avere la colorazione. Dal punto 2, vediamo che questo non può essere lo stesso colore come nessuno dei suoi vicini.

Nel passo tre facciamo al massimo $ k $ chiamate verso l'oracolo, e lo facciamo per ogni vertice in $ G $, quindi in totale facciamo al massimo chiamate $ (k + 1) n $ alla Oracle ( compresa la ricerca di $ k $).