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.