Problema de decisión de 3 colores

Question

El problema 3-COLOR toma como entrada un grafo y decide si puede ser coloreado usando sólo 3 colores de manera que no haya 2 nodos adyacentes con el mismo color.

La reducción de 3-SAT a 3-COLOR utiliza el siguiente gadget (ver más abajo) para representar una cláusula en la fórmula de 3-SAT.

Está claro que sólo existe una 3-coloración válida cuando al menos uno de los nodos x, y o z tiene el mismo color que T. Ahora, supongamos que los 3 literales son Falsos. Entonces, si los nodos x, y y z tienen el mismo color que el nodo F, no existe una tricoloración válida.

Sin embargo, para el algoritmo de 3 colores, el gadget es sólo un subgrafo. Incluso si x, y y z son Falsos, si los coloreamos igual que el nodo T, habría una coloración válida. No me queda claro que se pueda especificar en la entrada del algoritmo de 3 colores que si un literal es Falso/Verdadero, debe tener el mismo color que F/T.

Entonces, ¿cómo es válida la reducción?

Answer 1

En realidad, no hay 3 coloreados si los 3 literales están coloreados como F. Esto se debe a que el nodo después de la "fusión" será coloreado como F, mientras que el espacio en blanco debajo de la izquierda de T será como X. El nodo restante (superior izquierda de T) no puede tener ningún color válido en este caso.

Answer 2

Para cada variable y, construye dos vértices, uno para y y otro para ~y. Conecte tanto y como ~y a X, el único nodo global que está conectado en un triángulo con T(rue) y F(alse). Estas conexiones asegurarán que uno de {y,~y} obtiene un color de T y el otro obtiene un color de F. Esto es lo que te da la conexión entre una coloración y una asignación de verdad.

A continuación, se utiliza el gadget para conectar cada cláusula de la fórmula 3-SAT, utilizando los vértices literales adecuados. Cada gadget se conecta a la misma T global como se muestra en la imagen.