enter image description here

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$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.