4
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ What do you mean by "'far' from having a Hamiltonian path"? $\endgroup$ – argentpepper Apr 11 '13 at 20:12
11
$\begingroup$

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

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.