2

The correspondence is almost the same as your other question. Here, the starting node is specified, so you don't need a dummy node or dummy arcs out of the starting node. To go from H-path (with start $1$ and end $t$) to tour, insert arc $(t,1)$. To go from tour to H-path, remove the arc that enters $1$.


2

Q1. You need bidirectional arcs to and from the dummy node $n+1$ because you don't know ahead of time which directions are needed to complete the tour. Exactly one arc will enter the dummy, and exactly one arc will leave the dummy. Q2. The two problems are equivalent because the H-paths in $G$ and TSP tours in $G'$ are in one-to-one-correspondence, with the ...


Only top voted, non community-wiki answers of a minimum length are eligible