Partial Inverse Traveling Salesman Problem

This study explores the partial inverse traveling salesman problem (TSP). In partial inverse problems, the task is to modify the associated weight system as minimally as possible so that the given partial solution can become a part of an optimal one in a new instance. In partial inverse TSPs, the task is to determine a new edge weight system in which the given partial solution of TSP (the given sequence of consecutive edges) can be included in the minimum Hamiltonian cycle of a new instance. The objective can be measured by the difference between the original and new weight systems under a fixed norm. In this work, we introduce several variants of the partial inverse TSP and investigate their complexity status.