# Reducing directed hamiltonian cycle to graph coloring

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?

• Directed Hamiltonian cycle can be reduced to undirected HC and this can be reduce to SAT and finally SAT to 3Coloring.
– user742
Mar 26 '12 at 21:22
• @Saeed Do you have a link to how undirected HC is reduced to SAT? I've tried searching, but only managed to find the reduction the other way around, i.e. SAT -> HC.
– Johan Sannemo
Mar 26 '12 at 21:26
• I doubt there's anything more direct than HC -> circuit-SAT -> SAT.
– Ricky Demer
Mar 26 '12 at 21:33
• ps: any two $\sf{NP\text{-}complete}$ problems can be reduced to each other. Mar 26 '12 at 22:57
• I think the question should be rephrased to account for the fact that such a chain has to exist based because of prior knowledge and we are looking for a nice chain.
– Raphael
Mar 29 '12 at 9:26

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}$.
• Not sure the OP was asking for this, but can you give ideas or references for the reductions?
– Raphael
Mar 30 '12 at 7:20
• @Raphael, the second and third reductions are standard textbook exercises and are also in Karp's original paper. The first one is also easy (doesn't need Cook-Levin) and we often give similar problems as assignments, the key is to choose the right propositional variables (here use $p_{v,i}$ to state that $v$ is the $i$th variable in a sequence) and then express the condition that it is DHP as a polysize formula. But since OP only asked for a chain and not the details of them. Unless clarified by OP I think this answers the question. Mar 30 '12 at 16:39
• ps: it seems like an undergrad homework, I prefer to only give hints. Mar 30 '12 at 16:42