6
$\begingroup$

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?

$\endgroup$

migrated from cstheory.stackexchange.com Mar 29 '12 at 8:32

This question came from our site for theoretical computer scientists and researchers in related fields.

  • $\begingroup$ Directed Hamiltonian cycle can be reduced to undirected HC and this can be reduce to SAT and finally SAT to 3Coloring. $\endgroup$ – user742 Mar 26 '12 at 21:22
  • $\begingroup$ @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. $\endgroup$ – Johan Sannemo Mar 26 '12 at 21:26
  • $\begingroup$ I doubt there's anything more direct than HC -> circuit-SAT -> SAT. $\endgroup$ – Ricky Demer Mar 26 '12 at 21:33
  • 2
    $\begingroup$ ps: any two $\sf{NP\text{-}complete}$ problems can be reduced to each other. $\endgroup$ – Kaveh Mar 26 '12 at 22:57
  • 1
    $\begingroup$ 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. $\endgroup$ – Raphael Mar 29 '12 at 9:26
4
$\begingroup$

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}$.
$\endgroup$
  • $\begingroup$ Not sure the OP was asking for this, but can you give ideas or references for the reductions? $\endgroup$ – Raphael Mar 30 '12 at 7:20
  • 2
    $\begingroup$ @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. $\endgroup$ – Kaveh Mar 30 '12 at 16:39
  • $\begingroup$ ps: it seems like an undergrad homework, I prefer to only give hints. $\endgroup$ – Kaveh Mar 30 '12 at 16:42

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.