-4
$\begingroup$

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.

$\endgroup$

closed as off topic by Yuval Filmus, Jeffε, Dave Clarke Mar 22 '13 at 22:33

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Perhaps more appropriate to cs.stackexchange. $\endgroup$ – Yuval Filmus Mar 12 '13 at 16:17
  • $\begingroup$ 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 Computer Science which has a broader scope. $\endgroup$ – Kaveh Mar 12 '13 at 16:25
  • 3
    $\begingroup$ 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 Computer Science). Please don't do that. Read the faq and don't post questions on cstheory which are not in its scope. $\endgroup$ – Kaveh Mar 12 '13 at 16:41
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$.

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Kaveh Mar 12 '13 at 16:43

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