Complexity reductions to Hamiltonian Path?

Question

I am looking for a NP-hardness reduction from an arbitrary problem to the Hamiltonian Path problem such that the reduced no-instances of Hamiltonian path are "far" from having a Hamiltonian path.

Do you know such a reduction? Or does there exist a list of reductions to Hamiltonian Path somewhere?

Answer 1

For undirected graphs, you can build a graph $G$ for every constant $0<c<1$ from an $n$-variate CNF SAT instance $I$ such that

• $G$ has $N=\operatorname{poly}(n)$ vertices
• If $I$ is satisfiable, then $G$ has a Hamiltonian cycle
• If $I$ is not satisfiable, then $G$ has no path of length $N-N^c$.

Karger Motwani Ramkumar 1997

For directed graphs, you can build a graph $G$ for every constant $0<c<1$ from an $n$-variate CNF SAT instance $I$ such that

• $G$ has $N=\operatorname{poly}(n)$ vertices
• If $I$ is satisfiable, then $G$ has a Hamiltonian cycle
• If $I$ is not satisfiable, then $G$ has no path of length $N^{1-c}$.

Björklund Husfeldt Khanna 2004