1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ A fix: "adding one reverse edge for every edge ..." you prove the reduction FROM undirected Hamiltonian path TO directed Hamiltonian path (undirected HP $\leq_m^p$ directed HP). Now you need a reduction from directed to undirected ... $\endgroup$ – Vor Jan 28 '16 at 16:47
  • $\begingroup$ Hint 1: can you simulate the behavior of a directed graph with nodes having arbitrary indegree/outdegree with a directed graph in which for each node $indeg(u) + outdeg(u) \leq 3$ ? Hint 2: try to replicate what can happen on a node with $indeg(u) + outdeg(u) \leq 3$ using an undirected graph ... $\endgroup$ – Vor Jan 28 '16 at 17:31
  • $\begingroup$ Could you "encode" the direction of the graph as added nodes? Let's say we have a Graph a->b->c (directed). Now i want to simulate that with an undirected graph. We add nodes a_after, b_before, b_after, c_before and add the edges (a,a_after), (a_after,b_before),(b_before,b),(b,b_after),(b_after,c_before),(c_before,c). That should still be polynomial time, because you add at most 3 nodes and one edge per new node. $\endgroup$ – guest Jan 28 '16 at 17:44
  • $\begingroup$ Well, guys. I am pretty sure, that is goind to work. So thank you for your input! :) (I don't know how to mark your answer as answer though.) $\endgroup$ – guest Jan 28 '16 at 20:05

Your Answer

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

Browse other questions tagged or ask your own question.