<p>If you have a polynomial time oracle for solving an NP-hard problem, you can use it to solve any other problem in NP as well, including what you want in your "sequential algorithm": Given a graph and a path of length $i$, whether the given path can be completed to a Hamiltonian path.</p>

CC BY-SA 3.0
2013-03-12T15:29:46.123Z
2013-03-12T15:29:46.123Z
Mahdi Cheraghchi
<p>Given a polytime algorithm for HAMPATH, you can find a Hamiltonian path as follows. Start by guessing the initial and final vertices ($n(n-1)$ choices). We now try to uncover the path edge by edge. Given a path $p$, we need to determine whether it extends to a Hamiltonian path - and given such an oracle, we can find a Hamiltonian path by guessing the edges one at a time.</p>

<p>Given a path $p$ from $x$ to $y$, here is how to find out whether $p$ can be extended to a Hamiltonian path from $x$ to $z$ (recall we guessed the final vertex $z$ in advance). Remove all vertices in $p$ other than $y$ from the graph. Add a new vertex $a$ connected only to $y$, and a new vertex $b$ connected only to $z$. The new graph has a Hamiltonian path if and only if in the original graph, $p$ can be extended to a Hamiltonian path terminating at $z$.</p>

CC BY-SA 3.0
2013-03-12T16:43:01.777Z
If you think a question is off-topic please don't answer it on cstheory and wait till it is migrated to an appropriate site. Answering them on cstheory might encourage people to post more off-topic questions here.
Kaveh
CC BY-SA 3.0
2013-03-12T16:17:33.397Z
2013-03-12T16:17:33.397Z
Yuval Filmus
<p>Let us assume (probably wrongly) that P=NP, meaning that we know a way to output a hampath if it exists. </p>

<p>A graph has $n$ vertexes.</p>

<p>Can the algorithm that solves the problem be modified in polynomial time to an algorithm that solves the problem sequentially?</p>

<p>By sequentially, I mean that the algorithm solves the problem by this way: an algorithm first finds whether a path with two edges that do not return to any of vertexes already reached exists, and then uses information gathered in finding aforementioned case to find whether a path with three edges that do not return to any of vertexes already reached exists and so on until $n$ vertexes. </p>

CC BY-SA 3.0
2013-03-12T16:17:46.673Z
Perhaps more appropriate to cs.stackexchange.
Yuval Filmus
CC BY-SA 3.0
2013-03-12T16:25:59.037Z
Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Your question might be suitable for [cs.se] which has a broader scope.
Kaveh
CC BY-SA 3.0
2013-03-12T16:41:04.167Z
It seems that you have posted several questions that are not research level using different names in a short period of time (it also seems that you have posted similar questions under other names on [cs.se]). Please don't do that. Read the [faq] and don't post questions on cstheory which are not in its scope.
Kaveh
<cc.complexity-theory><graph-theory>
Polynomial algorithm for HAMPATH transformed into an algorithm that solves the problem sequentially?
user14159
# Polynomial algorithm for HAMPATH transformed into an algorithm that solves the problem sequentially?

(Asked by: username_0 on 2013-03-12)

Let us assume (probably wrongly) that P=NP, meaning that we know a way to output a hampath if it exists.

A graph has $n$ vertexes.

Can the algorithm that solves the problem be modified in polynomial time to an algorithm that solves the problem sequentially?

By sequentially, I mean that the algorithm solves the problem by this way: an algorithm first finds whether a path with two edges that do not return to any of vertexes already reached exists, and then uses information gathered in finding aforementioned case to find whether a path with three edges that do not return to any of vertexes already reached exists and so on until $n$ vertexes.

**Tags:** cc.complexity-theory, graph-theory

> **Comments:**
> **username_1**: Perhaps more appropriate to cs.stackexchange.  
> **username_2**: Welcome to cstheory, a Q&A site for *research-level* questions in *theoretical computer science* (TCS). Your question does not appear to be a research-level question in TCS. Please see the [FAQ] for more information on what is meant by this. Your question might be suitable for [cs.se] which has a broader scope.  
> **username_2**: It seems that you have posted several questions that are not research level using different names in a short period of time (it also seems that you have posted similar questions under other names on [cs.se]). Please don't do that. Read the [faq] and don't post questions on cstheory which are not in its scope.  

---

## 2 answers

### Answer by username_3 on 2013-03-12. Score: 1

If you have a polynomial time oracle for solving an NP-hard problem, you can use it to solve any other problem in NP as well, including what you want in your "sequential algorithm": Given a graph and a path of length $i$, whether the given path can be completed to a Hamiltonian path.


---

### Answer by username_1 on 2013-03-12. Score: 0

Given a polytime algorithm for HAMPATH, you can find a Hamiltonian path as follows. Start by guessing the initial and final vertices ($n(n-1)$ choices). We now try to uncover the path edge by edge. Given a path $p$, we need to determine whether it extends to a Hamiltonian path - and given such an oracle, we can find a Hamiltonian path by guessing the edges one at a time.

Given a path $p$ from $x$ to $y$, here is how to find out whether $p$ can be extended to a Hamiltonian path from $x$ to $z$ (recall we guessed the final vertex $z$ in advance). Remove all vertices in $p$ other than $y$ from the graph. Add a new vertex $a$ connected only to $y$, and a new vertex $b$ connected only to $z$. The new graph has a Hamiltonian path if and only if in the original graph, $p$ can be extended to a Hamiltonian path terminating at $z$.

> **Comments:**
> **username_2**: If you think a question is off-topic please don't answer it on cstheory and wait till it is migrated to an appropriate site. Answering them on cstheory might encourage people to post more off-topic questions here.  

---

