this is homework, so PLEASE do not give me the solution(!), but help me get there on my own.
I've got to proof that directed Hamilton Path with fixed stard and ending and undirected Hamilton Path with fixed start and ending are poly-time-equivalent.
I can do that for directed to undirected no problem by adding one reverse edge for every edge there is. That takes O(|E|) time, which is polynomial.
Now, I've got to show that there is a polynomial reduction from UNDIRECTED to DIRECTED Hamilton pahts, meaning that iff(!) I know that an undirected graph has a Hamiltonian Path from x to y, can I tweak it in polynomial time so that it is a directed graph with an Hamiltonian path from x to y?
I've tried doing it incrementally, starting with x then saving one alternate representation of the graph for every outgoing edge and deleting all edges that have been used. This is going to take non-detetministic space, so it is goind to take non-deterministic time, which indicates that that idea is crap.
I've tried just modifying the path itself and then noticed that that is not going to work, since getting the path is NP-hard.
Can anyone give me a hint?