Grafico 3-colorabilità è auto-riducibile

Question

Sono interessato a auto-riducibilità del grafico problema 3-Coloralibity.

Definizione di grafico 3-Coloralibity problema.

Dato un grafo non orientato $ G $ fa esiste un modo per colorare i nodi rosso, verde e blu in modo che nessun nodi adiacenti hanno lo stesso colore?

definizione di self-riducibilità.

Un linguaggio $ L $ è auto-riducibile se un oracolo macchina di Turing TM $ T $ esiste tale che $ L = L (T ^ L) $ e per ogni ingresso $ x $ lunghezza $ n $, $ T ^ L (x) $ interroga l'oracolo per le parole di lunghezza al massimo $ n-1 $.

vorrei mostrare in maniera molto rigorosa e formale che grafico 3-colorabilità è auto-riducibile.

Prova di auto-riducibilità del SAT può essere utilizzato come esempio ( auto- riducibilità di SAT ).

A mio parere, l'idea generale della prova di auto-riducibilità del grafico 3-colorabilità è diverso da prova di SAT auto-riducibilità in alcuni aspetti.

• SAT ha due scelte per ogni letterale (vero o falso) e grafico 3-colorabilità ha tre scelte (vale a dire, verde blu rosso).
• Le scelte di SAT letterale indipendenti l'uno dall'altro e scelte di colori di grafico 3 colorabilità sono strettamente dipendenti, ogni nodo adiacente deve avere colore diverso, questa struttura potenzialmente potrebbe contribuire a rendere meno iterazione tra tutti i colori.

L'idea generale della prova .

denotano Let da $ c_ {v_i} $ il colore del vertice $ v_i $, che può assumere uno dei seguenti valori (rosso, verde, blu). Definire grafo $ G '$ da un dato grafo $ G $ colorando l'arbitrario vertice $ V_0 $, assegnare $ c_ {V_0} $ a 'rosso' e mettere il grafo $ G' $ con colorato vertice $ V_0 $ all'ingresso dell'oracolo. Se oracolo risponde 1, il che significa che il grafico modificato è ancora 3-colorabile, salvare le assegnazioni correnti e inizia nuova iterazione, con la differente vertice $ v_1 $ scelta arbitrariamente, colore dei vertici $ v_1 $ secondo i colori dei vertici adiacenti. se oracolo risponde 0, che significa che il precedente assegnazione è rotto 3 colorabilità, scegliere il colore differente dal set di tre colori, ma sempre secondo i colori di vertici adiacenti.

La prova precedente non è matematica robusta, la domanda è come migliorare e per renderlo più formale e matematica rigorosa. Sembra che ho bisogno di più attenzione distinguere i casi in cui nuovo vertice non ha bordi con i vertici già colorati e quando il nuovo vertice è adiacente a vertici già colorati.

Inoltre vorrei dimostrare che grafico 3-colorabilità è auto-riducibile verso il basso.

Definizione del linguaggio di sé riducibile verso il basso.

La lingua $ A $ è detto di essere verso il basso auto-riducibile se è possibile determinare in tempo polinomiale se $ x \ in A $ utilizzando i risultati delle query più brevi.

L'idea sembra essere semplice ed intuitivo: iniziare con colorazione un vertice arbitrario, e ad ogni iterazione metti un vertice più colorato e controllare da oracolo se grafo è ancora 3-colorabile, se non colorazione inversa precedente e controllare un altro colore.

Ma come scrivere la prova in maniera rigorosa e più importante come trovare una codifica appropriata di un grafico.

In breve, vorrei mostrare che grafico 3-colorabilità è auto-riducibile e verso il basso auto-riducibile in maniera rigorosa e formale.

I apprezzeranno condividere i tuoi pensieri con noi.

Aggiornamento:

verso il basso auto-riducibilità

Verso il basso auto-riducibilità viene applicato al problema decisionale e di Oracle risponde lo stesso problema decisionale con l'input più breve, al termine del processo di discesa auto-riduzione dovremmo avere le assegnazioni dei colori a destra.

Ogni 3 - colorabile grafo $ G $ con più di tre vertici, ha due vertici $ x, y $ con lo stesso colore. A quanto pare, c'è solo tre colors e più di tre vertici così un numero di vertici non adiacenti potrebbero avere lo stesso colore. Se ci si fondono $ x $ e $ $ y con lo stesso colore come risultato abbiamo ancora 3 - grafico colorabile, proprio perché, se grafo è 3 - colorabile, poi ci sono esistere destra assegnazione di tutti i vertici che sono adiacenti a $ x $ e $ y $ secondo lo stesso colore di $ x, y $, così fondendo $ x, y $ non occorre cambiare qualsiasi colore di qualsiasi vertici, abbiamo solo bisogno di aggiungere più bordi tra vertici già colorati correttamente (lo so che non è la migliore spiegazione, io apprezzo se qualcuno potrebbe spiegare meglio). Su ogni iterazione prendiamo due vertici non adiacenti $ x, y $ il grafico $ G $, merge $ x $ e $ $ y e get grafo G $ '$ che è il nostro più corta ingresso al oracolo. Oracle risponde se è 3-colorabile o meno. Ora il problema è prima di $ G '$ sull'ingresso di Oracle dovrei colorare la fusione vertice e prova colorabilità di $ G' $, se non è 3-colorabile cambiare il colore, ma come implementare correttamente, di cui ho bisogno codificante per esso.

auto-riducibilità

In primo luogo, dovremmo controllare se un dato grafo $ G $ è 3-colorabile a tutti, quindi impostarlo su input di Oracle, Oracle e risponderà se è 3 - colorabile, se sì, quindi avviare il processo. Due vertici non adiacenti possono avere lo stesso colore grafico 3-colorabile. Il processo di auto-riducibilità dovremmo correre in iterazioni, penso che possiamo iniziare da piccoli sottografo $ G '$ di un dato grafo $ G $ e su ogni iterazione aggiungere uno più vertici di $ G $ a $ G' $. In Paralel, dovremmo mantenere l'assegnazione dei vertici già colorati. Purtroppo, ancora non capisco completamente l'idea. Gradirei aiuto e suggerimenti.

Answer 1

Come Vor cita nel suo commento, la tua riduzione non funziona, dal 3-colorabilità non accetta assegnazioni parziali di colori. Il problema è ancora più profondo, poiché impostare il colore di un singolo vertice non fa qualsiasi progressi nel determinare se il grafo è 3-colorabile: infatti, il grafico è 3-colorabile sse esiste un 3 -coloring in cui vertice $ v $ viene assegnato il colore $ c $, per qualsiasi $ v, c $ che si sceglie.

Ecco un suggerimento su come risolvere il vostro esercizio, seconda parte. In ogni 3-colorazione di un grafo G $ $ su più di tre vertici, ci sono due vertici $ x, y $ ottenendo lo stesso colore (perché?). Se noi fondiamo $ x $ e $ y $, il grafico risultante è ancora 3-colorabile (perché?). Prova ad utilizzare questa idea di costruire un ribasso algoritmo di auto-riduzione per il 3-colorabilità.

Modifica: Ed ecco un suggerimento su come risolvere l'esercizio, prima parte. Consideriamo due vertici non collegati $ x, y $. Se v'è una colorazione in cui ottengono lo stesso colore, allora $ G_ {xy} $ è 3-colorabile (perché?), E una colorazione di $ G $ possono essere estratti da una colorazione di $ G_ {xy} $ (come ?). Quando sarà questo stop processo?