Exploring the Parameterized Complexity of TSP Operators in Multi-Objective Optimization
TL;DR
It is proved that this problem is fixed-parameter tractable when parameterized by k, r, and the maximum edge weight W, and it is shown that parameterized analysis is a useful tool in this setting.
Abstract
Many real-world problems involve several objectives that conflict with each other. In such cases, the goal is not to find a single best solution, but a set of solutions that represent different trade-offs. Although parameterized complexity is a well-established framework for studying hard optimization problems, it has rarely been applied to multi-objective optimization. In this paper, we study the Multi-Objective Traveling Salesperson Problem (MO-TSP) from a parameterized complexity perspective. We focus on two common operators, namely 2-opt and swap. We consider restricted versions of these operators using a distance parameter r, and define (k,r)-neighborhoods that allow up to k applications of the operator. For both operators, we analyze the problem of finding an improved solution with respect to Pareto dominance. We prove that this problem is fixed-parameter tractable when parameterized by k, r, and the maximum edge weight W. These results provide new insight into the complexity of multi-objective optimization and show that parameterized analysis is a useful tool in this setting.