Homomorphism por un determinado gráfico NP-completo?

Question

Deje $G$ ser el siguiente Gráfico:

Queremos decidir si para una estructura de entrada $\mathcal{S}$ existe un homomorphism $S \to G$. Vamos a llamar a este problema $HOM_G$.

La tarea a la mano, es para mostrar que $HOM_G$ es NP-completo. Esto es un poco extraña, ya que $HOM_G$ no es un problema general, pero una muy específica.

Ya he hecho algunas observaciones: $HOM_G \in NP$ ya que si un potencial homomorphism es dado de que podamos decidir en el polinomio de tiempo si es correcto. Además, todos los ejemplos positivos de $\mathcal{S}$ tienen que ser los gráficos porque si hay un no-vacío de la no-binario o más, a continuación, una relación binaria no hay homomorphism a $G$.

Estoy un poco pegado a la derecha ahora. Alguna idea?

Answer 1

Por la reducción de 3-colorabilidad.

Este gráfico inyecta en su $G$ exactamente de tres maneras diferentes:

Si usted tiene un gráfico que desea 3-color, crear una copia de la anterior hexágono para cada uno de sus nodos, y representan a cada uno de sus extremos por dos sucesivos bordes -- por ejemplo, si el gráfico original es un cuadrado con la diagonal:

La dirección de los enlaces que representan el original bordes no importa, de cualquier manera, no permite que los vecinos de hexágonos para incrustar en $G$ en cualquiera de las dos diferentes maneras, pero no de la misma manera.

Por lo tanto no es un homomorphism de la ampliación de la gráfica de a $G$ exactamente si la gráfica original era de 3 engañosa.

(Idea parcial de crédito a @domotorp ahora eliminado respuesta).