Two graphs $G,H$ are homomorphically equivalent if there are exists a homomorphism from $G$ to $H$ and a homomorphism from $H$ to $G$.

The task is to prove that this decision problem $\mathrm{HOMEQUIV}$ is $NP$-complete.

Given a mapping $G \to H$ (or $H \to G$) it is possible to check whether it is an homomorphism in polynomial time. Thus, $\mathrm{HOMEQUIV} \in NP$.

Now I am looking for a suitable $NP$-complete problem with an elegant polynomial reduction to $\mathrm{HOMEQUIV}$. I was thinking about $\mathrm{3SAT}$ but I did not come up with a solution up until now.

There is a reduction to $3 ~ \mathrm{COLORING}$ which is pretty easy and I know from internet research that $\mathrm{3SAT} \leq_p 3 ~ \mathrm{COLORING}$. But I think this is cheating somehow because it is not a direct proof and it lacks the complicated part ($\mathrm{3SAT} \leq_p 3 ~ \mathrm{COLORING}$).

Any ideas for an elegant reduction?

  • $\begingroup$ There are numerous references showing that 3SAT reduces to 3COLORING, e.g. here or here. $\endgroup$ – rphv May 16 '13 at 18:13

David Eppstein provides a nice reduction from $\mathrm{CLIQUE}$ to $3 \mathrm{COLORING}$ such that

Given a graph $G$, we construct another graph $H$ such that $H$ is $n$-colorable if and only if $G$ has a $k$-Clique.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.