Reducing Path TSP to TSP

Vera Traub, Jens Vygen, Rico Zenklusen

We present a black-box reduction from the path version of the Traveling Salesman Problem (Path TSP) to the classical tour version (TSP). More precisely, we show that given an $\alpha$-a…