Reducing directed hamiltonian cycle to graph coloring

Problem Detail: 

The 3-SAT problem can be reduced to both the graph coloring and the directed hamiltonian cycle problem, but is there any chain of reductions which reduce directed hamiltonian cycle to graph coloring in polynomial time?

Asked By : Johan Sannemo

Answered By : Kaveh

Let $Q \in \sf{NP}$ and $Q' \in \sf{NP\text{-}hard}$. Then, by definition, $Q$ is (many-one) reducible to $Q'$ in polynomial time.

The exact chain of the reductions will depend on the $\sf{NP\text{-}hard}$ness proof of $Q'$. Typically, it is proven by a chain of reductions starting from $\mathrm{SAT}$ and ending with $Q'$ and then using the Cook-Levin theorem. So the chain of reductions will be a reduction from $Q$ to $\mathrm{SAT}$ followed by the chain of reductions from $\mathrm{SAT}$ to $Q'$.

There is usually a more direct reduction for specific problems (without using Cook-Levin), since it is usually easy to find a propositional formula directly expressing the required property (with no reference to TMs). For example, in the case of Directed Hamiltionian Path ($\mathrm{DHP}$) and Graph Coloring ($\mathrm{GC}$), you can reduce:

• $\mathrm{DHP}$ to $\mathrm{SAT}$,
• $\mathrm{SAT}$ to $\mathrm{3SAT}$,
• $\mathrm{3SAT}$ to $\mathrm{GC}$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/864