Reducing Prize-Collecting Stroll and Related Routing Problems to Prize-Collecting TSP (opens in new tab)

The prize-collecting stroll is the path version of the prize-collecting TSP. Given a complete metric graph, two prescribed terminal vertices $s,t$, and nonnegative penalties on vertices, the prize-collecting stroll asks for an $s$-$t$ tour minimizing the length of the tour plus the total penalty of vertices that are not visited by the $s,t$ tour. We study a common generalization of the prize-collecting stroll and several related prize-collecting...