I am currently studying the reduction from 3-SAT to the directed Hamiltonian cycle problem. During the process of the reduction,there is a step with the following:

If he have $k$ clauses in a $\phi$ formula with $n$ literals, we create $P_n$ paths and each $P_i$ path has at least $b$ nodes.

All the proofs I have found so far agree that $b > k$. But how much bigger? One option I found was $b=2k$. Another was $b=3k+3$. My question is, what is the best value for $b$, and how does a choice like that makes the proof easier or more difficult to make.

  • $\begingroup$ I'm not sure if it matters, as long as it is polynomially bounded? $\endgroup$ – Pieter21 Mar 15 '17 at 14:07
  • 1
    $\begingroup$ You probably ought to sketch how the particular reduction you're talking about goes. The one I can imagine has nothing in it that could be described as $P_n$ paths of at least $b>k$ nodes each. $\endgroup$ – Henning Makholm Mar 15 '17 at 15:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.