Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
Two questions:
Q1- Why do we need to add "bidirectional" arcs (instead of single directional arcs) between the new node n + 1 and with every node in the original network?
Q2- Why is the shortest H-path problem on an n-node network G is equivalent to an (n + 1)-node TSP on network G'?
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 same objective values. To go from H-path (with start $s$ and end $t$) to tour, insert arcs $(t,n+1)$ and $(n+1,s)$. To go from tour to H-path, remove the two arcs incident to $n+1$.
