On the generalized 2-Peripatetic Salesman Problem

Given an undirected graph the 2-Peripatetic Salesman Problem (PSP) is the problem that aims to minimize the total length of 2 edge-disjoint Hamiltonain cycles. The authors consider a generalization of the problem (GPSP), where each cycle visits each vertex at most (instead of exactly) once and a penalty has to be paid for each unvisisted vertex. They will show that the generalized problem can be solved by finding 2 edge-disjoint paths. The path problem in turn can be transformed into a standard PSP, so that the GPSP is solvable by a standard PSP algorithm. The authors will discuss some special cases of the GPSP.