I saw in Sipsers book the reduction from HAMPATH to UHAMPATH, when they converted every node in G (the directed) to 3 new nodes in G' (undirected).

Is there a reason they are using 3 nodes? why 2 isn't enough?

אשתדל לענות על כך ביום ראשון

Because 2 nodes is not enough :-)

I guess that your 2-node is approach is (for every v in V) to merge in the suggested reduction the nodes v_in and v_out, and to remove v_mid.

Ii this case, you are losing the guarantee that an (undirected) Hamiltonian path in G' can be translated into a (directed) path in G.

For instance consider the graph G = ({1,2,3},E), where E = (1,2), (3,2). It is clear that (G,s=1,t=3) is not in HAMPATH, but (G',s=1,t=3) is in UHAMPATH.

Iftach

I noticed that I my answer above explain why the reduction cannot do with one node (per original node), and not why it cannot do with two.

For the two-node case. consider the **directed** graph G described below which **has no Hamiltonian path from s to t**, and notice that your reduction (I I understand you correctly) maps G into an **undirected** graph that **has Hamiltonian path from s to t**.

The directed graph G to consider is (V,E), where V= {s,1,2,t} and E = {(1,s), (1,2),(2,1),(2,t), (t,2)}.

The above graph maps by your reduction into the undirected graph G'= (V',E'), where V'= {s,1i,1o,2i,2o,t} and E' = {(s,1o),(1i,2o),(2i,1o), (s,2i), (s,2o), (1i,1o),(2i,o),(2,t), (t,2)}.

Iftach

Oops, I got the reduction wrong, and the above is not a counter example. Will try to think more…

Another try (hopefully, Im not writing to myself :-))

The **directed** graph G to consider is (V,E), where V= {s,1,2,3,t} and E = {(s,1), (1,3),(1,t),(2,1), (3,2)}.

The above graph maps by your reduction into the **undirected** graph G'= (V',E'), where V'= {so,1i,1o,2i,2o,3i,3o,ti} and E' = {(s,1i),(1o,3i),(1o,ti), (2o,1i), (3o,2i), (1i,1o),(2i,2o), (3i,3o)}.

Indeed, G has no Hamiltonian from s to t (verify), but G' has Hamiltonian from so to ti (so,1i,2o,2i,3o,3i,1o,tin)

Iftach