Dos gráficos $G,H$ son homomórficamente equivalentes si existe un homomorfismo de $G$ a $H$ y un homomorfismo de $H$ a $G$ .
La tarea consiste en demostrar que este problema de decisión $\mathrm{HOMEQUIV}$ es $NP$ -completa.
Dado un mapeo $G \to H$ (o $H \to G$ ) es posible comprobar si es un homomorfismo en tiempo polinómico. Por lo tanto, $\mathrm{HOMEQUIV} \in NP$ .
Ahora estoy buscando un $NP$ -con una elegante reducción polinómica a $\mathrm{HOMEQUIV}$ . Estaba pensando en $\mathrm{3SAT}$ pero hasta ahora no he encontrado una solución.
Hay una reducción a $3 ~ \mathrm{COLORING}$ que es bastante fácil y sé por la investigación de Internet que $\mathrm{3SAT} \leq_p 3 ~ \mathrm{COLORING}$ . Pero creo que esto es engañar de alguna manera porque no es una prueba directa y le falta la parte complicada ( $\mathrm{3SAT} \leq_p 3 ~ \mathrm{COLORING}$ ).
¿Alguna idea para una reducción elegante?
