# 3-SAT to Hamiltonian cycle reduction

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.

• I'm not sure if it matters, as long as it is polynomially bounded? – Pieter21 Mar 15 '17 at 14:07
• 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. – Henning Makholm Mar 15 '17 at 15:31