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

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

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary;jsessionid=2819BBB1447F33A6A69B556B78508B5C?doi=10.1.1.52.8469">Karger Motwani Ramkumar 1997</a></p>

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

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

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.262">Björklund Husfeldt Khanna 2004</a></p>

CC BY-SA 3.0
2013-04-12T06:42:56.297Z
2013-04-12T06:42:56.297Z
Andreas Björklund
<p>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.</p>

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

CC BY-SA 3.0
2013-04-11T20:12:47.227Z
What do you mean by "'far' from having a Hamiltonian path"?
argentpepper
<cc.complexity-theory><np-hardness><reductions><hamiltonian-paths>
Complexity reductions to Hamiltonian Path?
jbensmai
# Complexity reductions to Hamiltonian Path?

(Asked by: username_0 on 2013-04-11)

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?

**Tags:** cc.complexity-theory, np-hardness, reductions, hamiltonian-paths
> **Comments:**
> **username_1**: What do you mean by "'far' from having a Hamiltonian path"?  

---

## 1 answers

### Answer by username_2 on 2013-04-12. Score: 11

For undirected graphs, you can build a graph $G$ for every constant $0

* $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](http://citeseerx.ist.psu.edu/viewdoc/summary;jsessionid=2819BBB1447F33A6A69B556B78508B5C?doi=10.1.1.52.8469)

For directed graphs, you can build a graph $G$ for every constant $0

* $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](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.105.262)


---

