Reducing directed hamiltonian cycle to graph coloring

Question

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?

Answer 1

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}$.