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?
$\begingroup$
$\endgroup$
9
-
$\begingroup$ Directed Hamiltonian cycle can be reduced to undirected HC and this can be reduce to SAT and finally SAT to 3Coloring. $\endgroup$– user742Mar 26, 2012 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 SannemoMar 26, 2012 at 21:26
-
$\begingroup$ I doubt there's anything more direct than HC -> circuit-SAT -> SAT. $\endgroup$– Ricky DemerMar 26, 2012 at 21:33
-
2$\begingroup$ ps: any two $\sf{NP\text{-}complete}$ problems can be reduced to each other. $\endgroup$– KavehMar 26, 2012 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, 2012 at 9:26
|
Show 4 more comments
1 Answer
$\begingroup$
$\endgroup$
3
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}$.
-
$\begingroup$ Not sure the OP was asking for this, but can you give ideas or references for the reductions? $\endgroup$– Raphael ♦Mar 30, 2012 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$– KavehMar 30, 2012 at 16:39
-
$\begingroup$ ps: it seems like an undergrad homework, I prefer to only give hints. $\endgroup$– KavehMar 30, 2012 at 16:42