# The Parameterized Complexity of Local Search for Multi-objective TSP

Julien Baste, Laetitia Jourdan, Marie-Eléonore Kessaci, Narges Tavassoli,
Marie-Emilie Voge

► To cite this version:

Julien Baste, Laetitia Jourdan, Marie-Eléonore Kessaci, Narges Tavassoli, Marie-Emilie Voge. The Parameterized Complexity of Local Search for Multi-objective TSP. European Symposium on Algorithms (Submitted), Sep 2025, Varsovie, Poland. hal-05080703

HAL Id: hal-05080703

https://hal.science/hal-05080703v1

Submitted on 22 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The Parameterized Complexity of Local Search for Multi-objective TSP

Julien Baste ✉ ID

CRISTAL, Université de Lille, France

Laetitia Jourdan ✉ ID

CRISTAL, Université de Lille, France

Marie-Eléonore Kessaci ✉ ID

CRISTAL, Université de Lille, France

Narges Tavassoli ✉

CRISTAL, Université de Lille, France

Marie-Emilie Voge ✉ ID

CRISTAL, Université de Lille, France

## Abstract

In this work, we extend the study of parameterized complexity to the domain of multi-objective combinatorial optimization, with a specific focus on the Multi-Objective Traveling Salesperson Problem (MO-TSP). While parameterized complexity has been widely explored for single-objective problems, to the best of our knowledge, it has not been applied in the context of multi-objective TSP. Our study investigates the parameterized complexity of MO-TSP with respect to local search neighborhood operators, specifically the “*r*-2-opt” and “*r*-swap” neighborhoods. We demonstrate that the problem is Fixed-Parameter Tractable (FPT) with respect to the parameters *k*, *r*, and *W*, which characterize the neighborhood operators used in local search. Here, *k* denotes the number of allowed operator applications, while *r* specifies the maximum allowed distance between the two edges (in the case of 2-opt) or the two vertices (in the case of swaps) involved in the move, and *W* denotes the maximum cost of traveling between any two cities in the TSP instance. Moreover, all the algorithms provided have linear dependency on the size of the input graph. These results provide a new theoretical foundation for understanding and designing efficient algorithms for MO-TSP, opening avenues for further research in parameterized multi-objective optimization.

**2012 ACM Subject Classification** Theory of computation → Fixed parameter tractability; Theory of computation → Design and analysis of algorithms

**Keywords and phrases** Parameterized Complexity, Multi-Objective, Local Search, Traveling Salesperson Problem, Fixed-Parameter Tractable

## 1 Introduction

Multi-objective optimization plays a critical role in solving real-world problems where trade-offs between competing objectives must be considered. Applications range from logistics and supply chain management to network design and robotics, where multiple, often conflicting, goals—such as cost, time, and resource efficiency—must be balanced. In such settings, local search heuristics have proven particularly effective due to their ability to quickly navigate large solution spaces and find high-quality solutions. Simultaneously, parameterized complexity has emerged as a robust theoretical framework for understanding and designing efficient algorithms for NP-hard problems. However, despite the importance of both fields, the intersection between parameterized complexity and multi-objective combinatorial optimization remains largely unexplored. This work aims to bridge this gap by focusing on the Multi-Objective Traveling Salesperson Problem (MO-TSP) as a representative case for applying parameterized complexity in multi-objective combinatorial optimization. We aim to gain practical efficiency

<figure><img src="image_2.png" /></figure>
## 23:2 The Parameterized Complexity of Local Search for Multi-objective TSP

and theoretical insights into the problem's structure by combining local search methods with parameterized analysis.

The Traveling Salesperson Problem (TSP) is a classic combinatorial optimization problem in which the goal is to determine the shortest possible route that allows a salesperson to visit each city exactly once and return to the starting point. Formally, given a set of cities $\{c_1, c_2, \dots, c_n\}$ and a distance function $d(c_i, c_j)$ that specifies the cost or distance between each pair of cities, the objective is to find a permutation $\pi$ of the cities that minimizes the total tour length: $\sum_{i=1}^{n-1} d(c_{\pi(i)}, c_{\pi(i+1)}) + d(c_{\pi(n)}, c_{\pi(1)})$. TSP stands as one of the most extensively explored problem in combinatorial optimization. It has served as a benchmark for algorithm development, with numerous algorithmic strategies either applied to it or inspired by it [8, 14].

In real-world applications, problems often involve balancing more than one objective. For example, in addition to minimizing the total travel distance, there may also be a need to minimize travel time, cost, or risk. This leads to the formulation of a Multi-Objective Optimization Problem (MO), where the goal is to optimize multiple conflicting objectives simultaneously. A general form of an MO can be expressed as:

$$ \text{minimize } \mathbf{F}(x) = (f_1(x), f_2(x), \dots, f_m(x)) \quad \text{subject to } x \in D, $$

where $\mathbf{F}(x)$ is a vector of $m \ge 2$ objective functions, $x = (x_1, x_2, \dots, x_n)$ is the decision variable vector, and $D$ represents the feasible solution space. In the context of TSP, $x$ is a permutation of the cities to be visited, and $n$ denotes the number of cities. We define the partial order $\prec$ between two solutions $x_1$ and $x_2$ in the objective space as follows:

$$ x_1 \prec x_2 \Leftrightarrow [\forall i \in \{1, \dots, m\} : f_i(x_1) \le f_i(x_2) \text{ and } \exists j \in \{1, \dots, m\} : f_j(x_1) < f_j(x_2)]. $$

If $x_1 \prec x_2$, we say that $x_1$ dominates $x_2$. Solving a multi-objective optimization problem aims to find all minimal elements under this partial order, collectively forming the Pareto front. These are the non-dominated solutions, meaning that no other feasible solution is strictly better in all objectives simultaneously [3]. For readability, this work mainly considers the Multi-Objective Traveling Salesperson Problem (MO-TSP) with two objectives, and Section sec:discussion presents how the results can be extended to any number of objectives.

A wide range of heuristic methods has been proposed and evaluated for the MO-TSP, many of which follow the local search paradigm—incrementally improving a candidate solution by exploring its nearby alternatives within a defined neighborhood. In the context of MO-TSP, local search techniques iteratively attempt to enhance the quality of a solution by applying minor modifications, such as city swaps or segment reversals, and assessing the impact on multiple objectives simultaneously. The search proceeds by moving from one solution to another within its neighborhood, guided by dominance-based comparisons or scalarization strategies to determine improvement [1, 10, 18]. Due to their simplicity and flexibility, local search algorithms are often used as stand-alone solvers or components within larger metaheuristic frameworks for refining the Pareto front [17]. Notable approaches include Pareto Local Search (PLS) [15], Pareto Archived Evolutionary Strategy (PAES) [11], Multi-Objective Tabu Search (MOTS) [9], and Pareto Simulated Annealing (PSA) [5]. These methods aim to efficiently explore the solution space while maintaining diversity in non-dominated solutions.

In parallel, parameterized complexity analyzes the computational difficulty of NP-hard problems by shifting the analytical focus from the total input size to the specific structural characteristics of the instance, known as parameters. Unlike classical complexity, which
considers all instances of the same input size equally difficult, parameterized analysis distinguishes between instances based on features such as solution size, graph width, or the number of constraints—attributes that often play a more significant role in determining computational hardness. Formally, a parameterized problem is defined as a language $L \subseteq \Sigma^* \times \mathbb{N}$, where each instance is a pair $(n, k)$, with $n$ representing the primary input and $k$ being the parameter. A problem is said to be Fixed-Parameter Tractable (FPT) if there exists an algorithm that can decide whether $(n, k) \in L$ in time $f(k) \cdot |n|^{O(1)}$, where $f$ is a computable function, and $|n|$ denotes the size of the input. The main idea here is that the combinatorial explosion is contained in the function $f$ that only depends on the parameter and not the input size [6]. This makes FPT algorithms impactful when dealing with small parameters. Parameterized complexity has demonstrated significant success in addressing single-objective combinatorial optimization problems by offering fine-grained analyses and enabling the design of more efficient algorithms. Within this framework, several powerful algorithmic techniques have emerged—such as bounded search trees, color-coding, kernelization, and iterative compression—that play a crucial role in tackling NP-hard problems [4]. Parameterized analysis of evolutionary algorithms has been applied to various important combinatorial optimization problems (see [16] for an overview). One of the earliest and most well-known applications was the classical Vertex Cover problem [13]. Subsequent studies have extended this approach to various other problems, including the Maximum Leaf Spanning Tree [12], Euclidean Traveling Salesperson Problem [19], and parameterized versions of the Makespan Scheduling problem [20]. A notable example is the application to the single-objective TSP, where $r$-swap local search neighborhoods have been systematically studied under this lens [7]. However, to the best of our knowledge, the application of parameterized complexity within the context of multi-objective optimization remains underexplored. Only a few studies have attempted to combine parameterized analysis with multi-objective frameworks. One notable example is the work by Baguley et al. [2], which employed Fixed-Parameter Multi-Objective Evolutionary Algorithms to address the $W$-Separator Problem. Given the additional layer of complexity introduced by multiple conflicting objectives, parameterized analysis holds strong potential for identifying which aspects of multi-objective problems contribute to their difficulty. It can guide the development of more efficient solution techniques, particularly for instances where the size alone is not an accurate indicator of complexity. This paper aims to bridge that gap by investigating how parameterized complexity can be applied to MO-TSP and provide a deeper understanding and algorithmic strategies for tackling this challenging class of problems.

**Main Contribution.** Despite the relevance and maturity of both parameterized complexity and multi-objective optimization, their integration has received little attention in the literature. This paper addresses this gap by introducing a parameterized complexity perspective to the study of local search methods in the context of the Multi-Objective Traveling Salesperson Problem. Specifically, we define and analyze two neighborhood operators—$r$-2-opt and $r$-swap—and provide FPT algorithms computing improving neighbors for each. We show that the problem is FPT with respect to the parameters $k, r$, and $W$ where $k$ indicates the number of permissible operator applications, $r$ bounds the distance between the elements (edges for 2-opt, vertices for swaps), and $W$ denotes the maximum weight across both objectives in the given TSP instance.

**Overview of the Paper.** The structure of this paper is as follows: Section 2 presents the necessary preliminaries, including formal definitions and notations relevant to the problem. Sections 3 and 4 provide a parameterized runtime analysis for the local search neighborhood operators “$r$-2-opt” and “$r$-swap,” respectively, with a focus on constructing improved
Hamiltonian cycles. Section 5 includes a discussion on extensions of the results of the previous sections. Finally, Section 6 concludes the paper, summarizing the main findings and outlining directions for future research.

## 2 Preliminaries

Given two integers $a$ and $b$, we denote by $[a, b]$ the set of every integer $x$ such that $a \le x \le b$. We denote by $\mathbb{N}$ the set of non-negative integers. Given $x$ and $y$ in $[1, n]$, we define $\text{dist}(x, y) = |x - y|$. A permutation of $[1, n]$ is a bijective function $\pi : [1, n] \to [1, n]$.

A graph $G$ is a pair $(V, E)$ where $V$ is a set of vertices and $E \subseteq V^2$ is the set of edges. In this paper, all the graphs are undirected and complete, i.e., $G = (V, E)$ where $E = V^2$. An Hamiltonian cycle of a graph $G$ is a cycle in $G$ that uses all the vertices. We will see the Hamiltonian cycle of a graph as a sequence of vertices. Given a complete graph $G$, every ordering of the vertices will correspond to a Hamiltonian cycle. As we need to keep track of both the graph and a Hamiltonian cycle at the same time, we define a $H$-ordered graph as the pair $H = (G = (V, E), S)$ where $G$ is a graph and $S$ is a sequence containing all the elements of $V$ exactly once. Given an $H$-ordered graph $H = (G = (V, E), S)$, we define the size of $H$ to be $|V|$ and $\text{Ham}(H)$ as the Hamiltonian cycle corresponding to $S$. Moreover, if $H$ has size $n$, we denote by $v_i^H$ the $i^{th}$ vertices of the sequence $S$ for each $i \in [1, n]$, $e_i^H = \{v_i^H, v_{i+1}^H\}$ for each $i \in [1, n-1]$ and $e_n^H = \{v_n^H, v_1^H\}$. When the context is clear, we may omit the exponent $H$ and write $v_i$ and $e_i$. Given an $H$-ordered graph $H = ((V, E), S)$ with two edge-weight functions $w_1$ and $w_2$, we denote by $W_{w_1,w_2}^H$ be the maximum weight associated to edges, $W_{w_1,w_2} := \max_{e \in E}\{w_1(e), w_2(e)\}$. When $H$, $w_1$, and $w_2$ are clear from the context we write $W$ instead of $W_{w_1,w_2}^H$.

We want to mention here that in this paper, we will consider the Hamiltonian cycles as sequences $(v_1, \dots, v_n)$. Thus, our definition implies that the distance between $v_1$ and $v_n$ is considered to be $n-1$ instead of the expected $1$, if we consider the distance inside the corresponding Hamiltonian cycle. Because of this, the neighborhood of a Hamiltonian cycle is the union of neighborhoods of all $H$-ordered graph representing this Hamiltonian cycle. This is discussed in Section 5 and solved by considering enough circular permutations of the sequence and calling the algorithm once for each permutation.

### 2.1 2-opt moves

Let $n$ be an integer. Given $x$ and $y$ two integers in $[1, n]$, with $x < y$, a $(x, y)$-2-opt move $\tau$ is a permutation of $[1, n]$ such that:

$$ \forall i \in [1, n] \quad \tau(i) = \begin{cases} x + y - i & \text{if } x \le i \le y, \\ i & \text{otherwise.} \end{cases} $$

Intuitively, for these indices $x$ and $y$ with $x < y$, it reverses the order of the subsequence $x, x+1, \dots, y$ while leaving all other elements unchanged. We define $\text{start}(\tau) = x$ and $\text{end}(\tau) = y+1$. Furthermore, we define an ordering relation $\le$ on 2-opt moves such that $\tau \le \tau'$ if and only if $\text{start}(\tau) \le \text{start}(\tau')$. By applying the $(x, y)$-2-opt $\tau$ to an $H$-ordered graph $H = (G, S)$, we mean that we create a new $H$-ordered graph $H' = (G, S')$ where $v_i^{H'} = v_{\tau(i)}^H$. A 2-opt move is a $(x, y)$-2-opt for some $x$ and $y$ in $[1, n]$. Moreover, if, for some integer $r$, the distance between $x$ and $y$ is less than or equal to $r$, we also say that it is a $r$-2-opt move.

Given an ordered sequence of 2-opt moves $Q$, we define the 2-opt graph $G^Q$ as follows: the vertex set is the set of each 2-opt in the sequence $Q$, and given two 2-opt moves $\tau_1$ and
$\tau_2$, an edge is added between them if $[\text{start}(\tau_1), \text{end}(\tau_1) - 1] \cap [\text{start}(\tau_2), \text{end}(\tau_2) - 1] \neq \emptyset$. Given an ordered sequence of 2-opt moves $Q$ and a set $X$ of 2-opt moves used in $Q$, we define $Q[X]$ as the subsequence of $Q$ restricted to elements of $X$.

We define *ordered sequence of r-2-opt moves* or *0r0* to be the set of all sequences $(\tau_1, \dots, \tau_p)$, where each element of the sequence is an *r-2-opt move*. We define the *connected ordering of r-2-opt moves* (abbreviated as *C0r0*) to be the set of all ordered sequences of *r-2-opt moves* $Q$ such that $G^Q$ is connected. We define *k-C0r0* as the set of all sequences that include all possible *C0r0* with up to $k$ elements. Applying a given ordered sequence $Q = (\tau_1, \dots, \tau_p) \in 0r0$ on an *H*-ordered graph *H*, means that we first apply $\tau_1$ to *H* and then, in the newly created *H*-ordered graph, we apply $\tau_2$ and so on until $\tau_p$. We define the *start* of $Q$, called *start*($Q$), to be $\min_{i \in [1, p]} \{\text{start}(\tau_i)\}$ and the *end* of $Q$, called *end*($Q$), to be $\max_{i \in [1, p]} \{\text{end}(\tau_i)\}$. We denote by $H^Q$ the graph obtained by applying $Q$ to *H*. Given an *H*-ordered graph $H = ((V, E), S)$, with $|V| = n$ and two edge-weight functions $w_i : E \to \mathbb{N}, i \in \{1, 2\}$, we define $f_i$ to be such that for each $Q \in 0r0$, $f_i(Q) := \sum_{j \in [1, n]} w_i(e_j^{H^Q}) - \sum_{j \in [1, n]} w_i(e_j^H)$ for $i \in \{1, 2\}$. We say that $Q \in 0r0$ improves *H* if $f_i(Q) < 0$ and $f_{3-i}(Q) \le 0$ where $i \in \{1, 2\}$. In simpler terms, this means the newly created Hamiltonian cycle is better than the initial one.

### 2.1.1 Example

Let $H = ((V, E), S)$ where $S = (v_1, v_2, \dots, v_8)$ be the *H*-ordered graph depicted in Figure 1 where we only draw the edges corresponding to the Hamiltonian cycle. After applying the (1,3)-2-opt move, we obtain $H' = ((V, E), S')$ where $S' = (v'_1, v'_2, \dots, v'_8) = (v_1, v_3, v_2, v_4, v_5, v_6, v_7, v_8)$ depicted in Figure 2. After applying the (3,5)-2-opt move to $H'$, we obtain $H'' = ((V, E), S'')$ where $S'' = (v''_1, v''_2, \dots, v''_8) = (v_1, v_3, v_2, v_5, v_4, v_6, v_7, v_8)$ depicted in Figure 3.

<figure><img src="image_3.png" /><figcaption>■ **Figure 1** *H*-ordered</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>■ **Figure 2** After applying the first 2-opt (1,3).</figcaption></figure>

<figure><img src="image_5.png" /><figcaption>■ **Figure 3** After applying both $((1,3), (3,5))$.</figcaption></figure>

## 2.2 *r*-swaps

For ease of readability, we provide a definition of *r*-swaps in a similar form to the one given for the 2-opt move. Let $n$ be an integer. Given $x$ and $y$ two integers in $[1, n]$, with $x < y$, a $(x, y)$-swap $\sigma$ is a permutation of $[1, n]$ such that $\sigma(x) = y$, $\sigma(y) = x$, and $\sigma(i) = i$ for $i \in [1, n] \setminus \{x, y\}$. Intuitively, for these indices $x$ and $y$ with $x < y$, it swaps $x$ and $y$ of the subsequence $x, x+1, \dots, y$ while leaving all other elements unchanged. We define
23:6 The Parameterized Complexity of Local Search for Multi-objective TSP

start(σ) = x and end(σ) = y. By applying the (x, y)-swap σ to an H-ordered graph H = (G, S), we mean that we create a new H-ordered graph H' = (G, S') where $v_i^{H'} = v_{\sigma(i)}^H$. Furthermore, we define an ordering relation ≤ on swaps such that σ ≤ σ' if and only if start(σ) ≤ start(σ'). A swap is a (x, y)-swap for some x and y in [1, n]. Moreover, if, for some integer r, the distance between x and y is less than or equal to r, we also say that it is an r-swap.

Given an ordered sequence of swaps S, we define the swap graph G^S as follows: the vertex set is the set of each swap in the sequence S and given two swaps σ₁ and σ₂, an edge is added between them if [start(σ₁) - 1, end(σ₁)] ∩ [start(σ₂) - 1, end(σ₂)] ≠ ∅.

We define the ordered sequence of r-swaps or OrS to be the set of all sequences (σ₁, ..., σₚ), where each element of the sequence is an r-swap. We define the connected ordering of r-swaps (abbreviated as COrS) to be the set of all ordered sequences of r-swaps S such that G^S is connected. We define k-COrS as the set of all sequences that include all possible COrS with up to k elements. Applying a given sequence of r-swaps S = (σ₁, ..., σₚ) ∈ OrS on an H-ordered graph H means, as for the 2-opt moves, that we first apply σ₁ to H and then, in the newly created H-ordered graph, we apply σ₂ and so on until σₚ. We define the start of S ∈ OrS, called start(S), to be minᵢ∈[1,ₚ]{start(σᵢ)} and the end of S, called end(S), to be maxᵢ∈[1,ₚ]{end(σᵢ)}.

Given $Q \in \text{OrS}$ and $H$ an $H$-ordered graph, we denote by $H^S$ the graph obtained by applying $S$ to $H$. Given an $H$-ordered graph $H = ((V, E), S)$, with $|V| = n$ and two edge-weight functions $w_i : E \to \mathbb{N}, i \in \{1, 2\}$, we define $f_i$ to be such that for each $S \in \text{OrS}$, $f_i(S) := \sum_{j \in [1, n]} w_i(e_j^{H^S}) - \sum_{j \in [1, n]} w_i(e_j^H)$ for $i \in \{1, 2\}$. We say that $Q \in \text{OrS}$ improves $H$ if $f_i(S) < 0$ and $f_{3-i}(S) \le 0$ where $i \in \{1, 2\}$.

2.2.1 Example

Let $H = ((V, E), S)$ where $S = (v_1, v_2, \dots, v_8)$ be the $H$-ordered graph depicted in Figure 4 where we only draw the edges corresponding to the Hamiltonian cycle. After applying the (1,4)-swap, we obtain $H' = ((V, E), S')$ where $S' = (v_4, v_2, v_3, v_1, v_5, v_6, v_7, v_8)$ depicted in Figure 5. After applying the (4,6)-swap to $H'$, we obtain $H'' = ((V, E), S'')$ where $S'' = (v_4, v_2, v_3, v_6, v_5, v_1, v_7, v_8)$ depicted in Figure 6.

<figure><img src="image_6.png" /><figcaption>■ **Figure 4** H-
ordered</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>■ **Figure 5** After applying the first swap (1, 4).</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>■ **Figure 6** After both applying $\{(1,4), (4,6)\}$.</figcaption></figure>

232

233

234

235

236

237

238

239
# 3 Local Multi-Objective TSP(r-2-opt)

In this section, we focus on the neighborhood operator named the 2-opt move, and present a parameterized version of it. Here, H-ordered graphs are considered neighbors if one can be obtained from the other by applying at most *k* r-2-opt. Formally, the problem is as follows.

**LOCAL MO-TSP(r-2-OPT)**

**Input:** An H-ordered graph $H = ((V, E), S)$, two edge weight functions $w_1$ and $w_2$, and a positive integer $k$.

**Question:** Does there exist an ordered sequence of r-2-opt moves $Q$ of size at most $k$ such that $Q$ improves $H$?

Next, we present an algorithm and analyze its running time. This algorithm can be used to find the neighbors of the initial Hamiltonian cycle described in the decision problem above.

**► Theorem 1.** *LOCAL MO-TSP(r-2-OPT) is fixed-parameter tractable with respect to the combined parameters (k, r, W). It is solvable in time $O((k+1)! \cdot r^{2k-1} \cdot n + r \cdot k^5 \cdot W^4 \cdot n)$.*

**Proof.** Let $(H = ((V, E), S), w_1, w_2, k)$ represent an instance of the Local MO-TSP(r-2-opt) problem where $H$ is of size $n$. Our goal is to find a solution $Q$, which is a sequence of at most $k$ r-2-opt, such that $Q$ improves $H$.

The algorithm is divided into two main phases. The first phase employs a branching strategy to enumerate all k-CorO sequences. The second phase applies dynamic programming to combine these sequences and explore candidate solutions efficiently.

We start by explaining the first phase of the algorithm. We define $\lambda: [1, n] \times [1, n+1] \times \mathbb{Z}^2 \to k-CorO \cup \{\perp\}$ such that for each $(\alpha, \beta, d_1, d_2) \in [1, n] \times [1, n+1] \times \mathbb{Z}^2$, $\lambda(\alpha, \beta, d_1, d_2)$ is the shortest sequence $Q$ such that $Q$ is in k-CorO, $start(Q) = \alpha$, $end(Q) = \beta$, $f_1(Q) = d_1$ and $f_2(Q) = d_2$ or $\perp$ if no such sequence exists. We will see the function $\lambda$ as a table, and the goal of this first phase is to fill this table. First, note that, $Q$ has to be a k-CorO - at most $k$ 2-opt moves each of them at distance at most $r$ and connected, it means that $end(Q) - start(Q) \le k \cdot r$. Second, assuming that the maximum possible edge weight is $W$, the weight change resulting from a single 2-opt move lies within the interval $[-2W, 2W]$. For a sequence of $k$ 2-opt moves, the total weight change is therefore bounded within $[-2kW, 2kW]$. Thus, given $(\alpha, \beta) \in [1, n] \times [1, n+1]$ and $(d_1, d_2) \in \mathbb{Z}^2$, if $\alpha > \beta$, $\beta - \alpha > k \cdot r$, $|d_1| > 2kW$, or $|d_2| > 2kW$, we know that $\lambda_{(\alpha, \beta)}(d_1, d_2) = \perp$. We can then restrict our computation of $\lambda$ to $\beta - \alpha \le k \cdot r$, $|d_1| \le 2kW$, and $|d_2| \le 2kW$.

We now explain how to compute $\lambda$. In order to do so, we fix $\alpha \in [1, n]$ as the first parameter, and we generate all possible sequences $Q$ in k-CorO that start with $\alpha$. We first guess the size of $Q$ to be between 0 and $k$, which gives $k+1$ possibilities. Then, assume that $Q$ contains the r-2-opt moves $\tau_1, \dots, \tau_t$ with $t \le k$ and $\tau_1 \le \tau_2 \le \dots \le \tau_t$. By definition, we know that for each $i \in [1, t-1]$, $start(\tau_i) \le start(\tau_{i+1}) \le start(\tau_i) + r$. Thanks to this, and the fact that $start(\tau_1) = \alpha$, we know that we only have $(r+1)^{t-1}$ possibilities for finding $start(\tau_1), \dots, start(\tau_t)$. Moreover, for each $\tau_i$, $i \in [1, t]$, knowing $start(\tau_i)$, we have at most $r$ possibilities for finding $end(\tau_i)$, then we have $(r)^t$ possibilities for finding $end(\tau_1), \dots, end(\tau_t)$. We can then test all the possible orderings involving $\tau_1, \dots, \tau_t$, that is at most $t!$. Doing so, we obtain at most $(k+1) \cdot t! \cdot (r+1)^{2t-1}$ possible sequences $Q$ of k-CorO that start with $\alpha$. For each of them, we compute the associated values $\beta, d_1$, and $d_2$ and add it to the table $\lambda$ at position $(\alpha, \beta, d_1, d_2)$ if currently $\lambda(\alpha, \beta, d_1, d_2)$ is $\perp$ or contains
a longer sequence than $Q$. As this operation need to be done for each $\alpha$ in $[1, n]$, filling the table $\lambda$ takes $O((k+1)! \cdot (r+1)^{2k-1} \cdot n)$ steps.

We now explain the second phase of the algorithm. First, assume that $Q$ is an ordered sequence of 2-opt moves and let $G^Q$ be the associated 2-opt graph. We assume that $G^Q$ has $t$ connected components with vertex sets $X_1, \dots, X_t$. Without loss of generality, we assume that $\text{start}(Q[X_1]) \le \text{start}(Q[X_2]) \le \dots \le \text{start}(Q[X_t])$. As for each $i \in [1, t-1]$, $X_i$ and $X_{i+1}$ correspond to distinct connected components, we have, by definition of $G^Q$, that $\text{end}(Q[X_i]) \le \text{start}(Q[X_{i+1}])$. Note that for $i \in [1, t]$, the 2-opt moves in $X_i$ only affect the edges in $\{e_i^H \mid i \in [\text{start}(Q[X_i]), \text{end}(Q[X_i])-1]\}$. Using this, we have that $f_1(Q) = \sum_{i \in [1,t]} f_1(Q[X_i])$, and the same happens for $f_2$. Moreover, let $Q'$ be the sequence corresponding to $Q[X_1]$ followed by $Q[X_2]$ and so one until $Q[X_t]$. Then $f_1(Q') = f_1(Q)$ and $f_2(Q') = f_2(Q)$. In the following, we will use this property by constructing progressively the wanted ordered sequences using the fact that each $Q[X]$, where $Q$ is an ordered sequence of $r$-2-opt moves of length at most $k$ and $X$ is a connected component of $G^Q$, is already computed and stored in $\lambda$.

We then proceed to describe a dynamic programming algorithm to finish the work. We define, for each $\beta \in [1, n+1]$, the function $\text{dp}_\beta : \mathbb{Z}^2 \to k-0\text{r0} \cup \{\perp\}$ defined such that for each $(d_1, d_2) \in \mathbb{Z}^2$, $\text{dp}_\beta(d_1, d_2)$ is the shortest sequence $Q$ such that $Q$ is in $k-0\text{r0}$, $\text{end}(Q) \le \beta$, $f_1(Q) = d_1$ and $f_2(Q) = d_2$ or $\perp$ if no such sequence exists. For the same reason as before, we can then restrict ourselves to $|d_1| \le 2kW$, and $|d_2| \le 2kW$. With this definition, LOCAL MO-TSP($r$-2-OPT) has a positive answer if there exists $(d_1, d_2) \in [0, 2kW]^2 \setminus (0, 0)$ such that $\text{dp}_{n+1}(d_1, d_2) \ne \perp$.

First we fix $\text{dp}_1(0, 0) = ()$, where $()$ denote the empty sequence, and for each $(d_1, d_2) \in [-2kW, 2kW]^2 \setminus (0, 0)$, $\text{dp}_1(d_1, d_2) = \perp$. Indeed, the only ordered sequence of 2-opt move $Q$ such that $\text{end}(Q) \le 1$ is the empty sequence.

Let $\beta$ be an integer in $[2, n+1]$ and assume that for each $\beta' \in [1, \beta-1]$, $\text{dp}_{\beta'}$ has already been computed correctly, then we compute $\text{dp}_\beta$ as follows. For each $(d_1, d_2) \in [-2kW, 2kW]^2$, in order to determine $\text{dp}_\beta(d_1, d_2)$, we construct a set $S$ containing:

- $\text{dp}_{\beta-1}(d_1, d_2)$, if it is not $\perp$,

- $\text{dp}_\delta(d'_1, d'_2)$ concatenated with the sequence $\lambda(\delta, \beta, d''_1, d''_2)$,

if both $\text{dp}_\delta(d'_1, d'_2)$ and $\lambda(\delta, \beta, d''_1, d''_2)$ are different than $\perp$,

for each $(\delta, d'_1, d''_1, d'_2, d''_2) \in [\max(1, \beta-k \cdot r), \beta-1] \times [-2kW, 2kW]^4$ such that $d'_1+d''_1 = d_1$

and $d'_2+d''_2 = d_2$.

From all the sequences in $S$, we take the shortest one $Q$ and set $\text{dp}_\beta(d_1, d_2)$ to be $Q$. If the set $S$ is empty, then $\text{dp}_\beta(d_1, d_2)$ is $\perp$. In term of running time, computing $\text{dp}_{\beta-1}(d_1, d_2)$ takes $O(k \cdot r \cdot (4kW)^2)$ steps, indeed, there are $k \cdot r$ possible values for $\delta$, $4kW$ possible values for the pair $(d'_1, d''_1)$, and $4kW$ possible values for the pair $(d'_2, d''_2)$. This computation has to be done for the $(4kW)^2$ possibles values of $(d_1, d_2)$ and for every $\beta \in [2, n+1]$. Thus, the running time for this dynamic programming algorithm part is $O(r \cdot k^5 \cdot W^4 \cdot n)$.

With respect to the correctness of the computation, let $Q$ be a sequence that can be present in $\text{dp}_\beta(d_1, d_2)$. If $\text{end}(Q) < \beta$ then $Q$, or an equivalent has been computed using $\text{dp}_{\beta-1}(d_1, d_2)$. Otherwise let $X$ be the component of $G^Q$ such that $\text{end}(Q[X]) = \beta$ and $Y$ be the union of all other components. Then $Q$ is the concatenation of $Q[Y]$ with $Q[X]$. Let $\delta = \text{start}(Q[X])$, then $Q[X]$, or an equivalent, has been computed by $\lambda(\delta, \beta, d''_1, d''_2)$ for some $d''_1 = f_1(Q[X])$ and $d''_2 = f_2(Q[X])$, and $Q[Y]$, or an equivalent, has been computed by $\text{dp}_\delta(d'_1, d'_2)$ for $d'_1 = f_1(Q[Y])$ and $d'_2 = f_2(Q[Y])$. Thus $Q$, or an equivalent solution, has been added to $\text{dp}_\beta(d_1, d_2)$. As each of the considered elements for filling $\text{dp}_\beta(d_1, d_2)$ respects the constraint imposed by the definition of $\text{dp}_\beta$, the tables $\text{dp}_\beta$, $\beta \in [1, n+1]$ have been
constructed correctly.

We are now considering the complete running time of the algorithm. The algorithm has two parts, the first using $O((k+1)! \cdot (r+1)^{2k-1} \cdot n)$ steps and the second using $O(r \cdot k^5 \cdot W^4 \cdot n)$ steps. The theorem follows. ►

# 4 Local Multi-Objective TSP(r-swaps)

In this section, we focus on another widely used neighborhood operator, namely the swaps, and present a parameterized version of it. Here, two H-ordered graphs are considered neighbors if one can be obtained from the other by applying at most k r-swaps. As for each r-swaps, up to 4 edges are involved instead of 2 for the 2-opt, to keep the approach as similar as possible than the one used in Section 3, we present and solve a restricted version of LOCAL MO-TSP(r-SWAP) that prevent the first vertex of the H-ordered graph sequence to be in any swap. The problem is formally defined as follows.

**RESTRICTED LOCAL MO-TSP(r-SWAP)**

**Input:** An H-ordered graph $H = ((V, E), S)$, two edge weight functions $w_1$ and $w_2$, and a positive integer $k$.

**Question:** Does there exist an ordered sequence of r-swaps $Q$, that does not contains $v_1^H$, of size at most $k$ such that $Q$ improves $H$?

We want to mention that, as discussed later in Section 5, excluding $v_1^H$ of the swaps has no impact on the search for the neighborhood of the Hamiltonian cycle represented by $H$.

Next, we present the algorithm and its running time, which can be used to find a solution to the question above.

**► Theorem 2.** *RESTRICTED LOCAL MO-TSP(r-SWAP) is fixed-parameter tractable with respect to the combined parameter $(k, r, W)$. It is solvable in time $O((k+1)! \cdot r^{2k-1} \cdot n + r \cdot k^5 \cdot W^4 \cdot n)$.*

**Proof.** Let $(H = (V, E), S), w_1, w_2, k)$ represent an instance of the RESTRICTED LOCAL MO-TSP(r-SWAP) problem where $H$ is of size $n$. Our goal is to find a solution $Q$, which is a sequence of at most $k$ r-swaps, such that $Q$ improves $H$. The algorithm presented in this section has the same structure as the one presented in Section 3, in particular, it is divided into two main phases, one that enumerates all $k$-COrS sequences and another that combines these sequences to obtain the solution.

We start by explaining the first phase of the algorithm. We define $\lambda : [2, n]^2 \times \mathbb{Z}^2 \rightarrow k$-COrS $\cup \{\perp\}$ such that for each $(\alpha, \beta, d_1, d_2) \in [2, n]^2 \times \mathbb{Z}^2$, $\lambda(\alpha, \beta, d_1, d_2)$ is a shortest sequence $Q$ such that $Q$ is in $k$-COrS, $start(Q) = \alpha$, $end(Q) = \beta$, $f_1(Q) = d_1$ and $f_2(Q) = d_2$ or $\perp$ if no such sequence exists. Note that as $v_1^H$ should not be swapped, we have that $\alpha \ge 2$ and $\beta \ge 2$. As $Q$ has to be a $k$-COrS, then by definition, we have that $end(Q) - start(Q) \le k \cdot (r+1)$. Moreover, each swap removes up to four edges and add back the same number of edges, this implies that, using $W$ as the maximum possible edge weight, the weight change resulting from a single swap lies within the interval $[-4W, 4W]$. For a sequence of $k$ swaps, the total weight change is therefore bounded within $[-4kW, 4kW]$. Thus, given $(\alpha, \beta) \in [2, n]^2$ and $(d_1, d_2) \in \mathbb{Z}^2$, if $\alpha > \beta$, $\beta - \alpha > k \cdot (r+1)$, $|d_1| > 4kW$, or $|d_2| > 4kW$, we know that $\lambda(\alpha, \beta, d_1, d_2) = \perp$. We can then restrict our computation of $\lambda$ to $\beta - \alpha \le k \cdot (r+1)$, $|d_1| \le 4kW$, and $|d_2| \le 4kW$.
23:10 The Parameterized Complexity of Local Search for Multi-objective TSP

We now explain how to compute $\lambda$. Using the same strategy than in Section 3, for each $\alpha \in [2, n]$ as first parameter, we generate all possible sequences $Q$ in $k$-COrS that start with $\alpha$. Doing so, we fill the table $\lambda$ using $O((k+1)! \cdot (r+1)^{2k-1} \cdot n)$ steps.

For the second phase of the algorithm, let's see the main changes from the previous algorithm. Let $Q$ be an ordered sequence of swaps, let $G^Q$ be the associated swap graph, assume that $G^Q$ has $t$ connected components with vertex sets $X_1, \dots, X_t$ such that, without lost of generality, $\text{start}(Q[X_1]) \le \text{start}(Q[X_2]) \le \dots \le \text{start}(Q[X_t])$. As for each $i \in [1, t-1]$, $X_i$ and $X_{i+1}$ correspond to distinct connected components, we have, by definition of $G^Q$, that $\text{end}(Q[X_i]) < \text{start}(Q[X_{i+1}]) - 1$. Note that for $i \in [1, t]$, the swaps in $X_i$ only affect the edges in $\{e_i^H | i \in [\text{start}(Q[X_i]) - 1, \text{end}(Q[X_i])]\}$. But with this definition we also have that $f_1(Q) = \sum_{i \in [1, t]} f_1(Q[X_i])$, and the same for $f_2$.

For the dynamic programming part, we define, for each $\beta \in [2, n]$, the function $dp_\beta: \mathbb{Z}^2 \to k$-OrS $\cup \{\perp\}$ defined such that for each $(d_1, d_2) \in \mathbb{Z}^2$, $dp_\beta(d_1, d_2)$ is the shortest sequence $Q$ such that $Q$ is in $k$-OrS, $\text{end}(Q) \le \beta$, $f_1(Q) = d_1$ and $f_2(Q) = d_2$ or $\perp$ if no such sequence exists. Being careful with the indices, we fill the table in the same spirit that it is done in Section 3 in time $O(r \cdot k^5 \cdot W^4 \cdot n)$.

Again, combining the two parts, the first using $O((k+1)! \cdot (r+1)^{2k-1} \cdot n)$ steps and the second using $O(r \cdot k^5 \cdot W^4 \cdot n)$ steps we obtain the theorem. $\quad$

5 Discussion

**Extension to more than 2 objectives.** While Theorem 1 and Theorem 2 have been proved for two objectives in order to simplify the proofs, one can check that they can be extended to any $m$ objectives with $m \ge 2$. We then obtain the following theorems.

**Theorem 3.** *LOCAL MO-TSP(r-2-OPT) with $m$ objectives, $m \ge 2$, is fixed-parameter tractable with respect to the combined parameters $(k, r, W)$. It is solvable in time $O((k+1)! \cdot r^{2k-1} \cdot n + r \cdot k \cdot (k \cdot W)^{2m} \cdot n)$.*

**Theorem 4.** *RESTRICTED LOCAL MO-TSP(r-SWAP) with $m$ objectives, $m \ge 2$, is fixed-parameter tractable with respect to the combined parameter $(k, r, W)$. It is solvable in time $O((k+1)! \cdot r^{2k-1} \cdot n + r \cdot k \cdot (k \cdot W)^{2m} \cdot n)$.*

**Hamiltonian cycle as a cycle.** As discussed in Section 2, in this work, given a graph $G$ of size $n$, we consider the Hamiltonian cycle as a sequence $S = (v_1, \dots, v_n)$ through the $H$-ordered graph $H = (G, S)$, and use operations on $H$ to create a new Hamiltonian cycle. By definition, the neighborhood of the Hamiltonian cycle $C$ corresponds to the union of the neighborhoods of all $H$-ordered graphs representing this cycle. Let $C'$ be a Hamiltonian cycle in the neighborhood of $C$. By definition, there exists $H = (G, S)$, an $H$-ordered graph corresponding to $C$ and $Q \in k$-Or0 (resp. $Q \in k$-OrS) a sequence such that $H^Q$ corresponds to $C'$. Then, by definition of $k$-Or0 (resp. $k$-OrS), assuming $n > k \cdot (r+2)$, any interval $[z - k \cdot (r+2), z]$, $z \in [1, n]$, contains either 1 or an integer that is not within the range of any of the connected components of $G^Q$, where $G^Q$ is the 2-opt graph (resp. the swap graph). Thus, starting from any $H$-ordered graph $H' = (G, S')$ representing $C$ and testing the $k \cdot (r+2) + 1$ first rotations of $S'$ would ensure to find an $H$-ordered graph $H_0$ and a sequence $Q_0 \in k$-Or0 (resp. $Q_0 \in k$-OrS) such that $H_0^{Q_0}$ corresponds to $C'$.

Thanks to this observation, we removed the issue associated with considering the Hamiltonian cycle as a sequence in both LOCAL MO-TSP(r-2-OPT) and RESTRICTED LOCAL MO-TSP(r-SWAP).
MO-TSP(r-SWAP), or forcing $v_1^H$ not to be in any r-swap in RESTRICTED LOCAL MO-TSP(r-SWAP). Moreover, it only adds a factor $O(k \cdot r)$ into the computation, instead of a factor $O(n)$.

412

413

414

**In oriented graphs.** If we consider oriented graphs, two situations appear. For the swaps, nothing changes as for each swap, we still maintain the fact that at most 4 edges are removed and the same number of edges are added back. Thus, we have the following.

415

416

417

**► Theorem 5.** LOCAL MO-TSP(r-2-OPT) with *m* objectives, *m* ≥ 2, and where the input graph is directed, is fixed-parameter tractable with respect to the combined parameters (k, r, W). It is solvable in time $O((k+1)! \cdot r^{2k-1} \cdot n + r \cdot k \cdot (k \cdot W)^{2m} \cdot n)$.

418

419

420

For the 2-opt moves, the situation is a bit different. Indeed, if $\tau$ is a (x, y)-2-opt move, then all the elements between x and y are explored in the reversed order, implying that the corresponding edges should be reversed. Using the fact that we consider r-2-opt moves, the potential change provided by a r-2-opt is then within $[-(r+1)W, (r+1)W]$. Injecting this into the proof of Section 3, we obtain the following.

421

422

423

424

425

**► Theorem 6.** LOCAL MO-TSP(r-2-OPT) with *m* objectives, *m* ≥ 2, and where the input graph is directed, is fixed-parameter tractable with respect to the combined parameters (k, r, W). It is solvable in time $O((k+1)! \cdot r^{2k-1} \cdot n + r \cdot k \cdot (k \cdot (r+1) \cdot W)^{2m} \cdot n)$.

426

427

428

# 6 Conclusion

429

In this work, we presented a proof of concept for applying parameterized complexity theory to multi-objective combinatorial optimization, focusing on the Multi-Objective Traveling Salesperson Problem (MO-TSP). We demonstrated that local search problems based on the r-2-opt and r-swap neighborhood operators are Fixed-Parameter Tractable (FPT) with respect to key parameters *k*, *r*, and *W*.

430

431

432

433

434

As a next step, this theoretical foundation should be validated through empirical experiments. Although it is commonly observed that 2-opt outperforms swap in practical applications, our theoretical analysis reveals that the parameterized runtime complexities of local MO-TSP(r-swap) and local MO-TSP(r-2-opt) are nearly equivalent. Future research will focus on determining whether r-2-opt maintains its practical advantage over r-swap with respect to solution quality and convergence.

435

436

437

438

439

440

An interesting direction for future research is the integration of these local search strategies into evolutionary algorithms for computing the Pareto front in MO-TSP and comparing their empirical performance with existing methods. We believe that parameterized complexity provides a promising and largely unexplored framework for advancing algorithmic strategies in multi-objective optimization.

441

442

443

444

# References

445

1. E. Angel, V. Zissimopoulos, and C. Papadimitriou. Multi-objective local search for the traveling salesman problem with profits. *Journal of Heuristics*, 10(3):269-287, 2004.

447

448

2. S. Baguley, T. Friedrich, A. Neumann, F. Neumann, M. Pappik, and Z. Zeif. Fixed parameter multi-objective evolutionary algorithms for the w-separator problem. GECCO '23, page 1537-1545, New York, NY, USA, 2023. Association for Computing Machinery. doi:10.1145/3583131.3590501.

449

450

451

452

3. C.A. Coello Coello, C. Dhaenens, and L. Jourdan, editors. *The Multiobjective Traveling Salesman Problem: A Survey and a New Approach*. Springer, Berlin, Heidelberg, 2010.

453

454
23:12 The Parameterized Complexity of Local Search for Multi-objective TSP

455

456

4 M. Cygan, F. V. Fomin, Ł. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. *Parameterized Algorithms*. Springer, New York, 2016.

457

458

459

5 P. Czyżak and A. Jaszkiewicz. Pareto simulated annealing—a metaheuristic technique for multiple-objective combinatorial optimization. *Journal of Multi-criteria Decision Analysis*, 7:34–47, 1998. URL: https://api.semanticscholar.org/CorpusID:123140619.

460

461

6 R. G. Downey and M. R. Fellows. *Parameterized Complexity*. Springer-Verlag, New York, 1999.

462

463

7 J. Guo, S. Hartung, R. Niedermeier, and O. Suchý. The Parameterized Complexity of Local Search for TSP, More Refined. Algorithmica, Yokohama, Japan, 2011. Springer.

464

465

8 G. Gutin and A. Punnen, editors. *The Traveling Salesman Problem and Its Variations*. Kluwer Academic, London, 2001.

466

467

9 M. Hansen. Tabu search for multiobjective optimization: Mots. *Proceedings of the 13th International Conference on Multiple Criteria Decision Making*, 1997.

468

469

10 A. Jaszkiewicz. Genetic local search for multi-objective combinatorial optimization. In *European Journal of Operational Research*, pages 50–71. Elsevier, 2002.

470

471

472

11 J. D. Knowles and D. W. Corne. The pareto archived evolution strategy: A new baseline algorithm for multiobjective optimisation. In *Proceedings of the 1999 Congress on Evolutionary Computation (CEC'99)*, pages 98–105, United States, 1999. IEEE.

473

474

475

12 S. Kratsch, P. K. Lehre, F. Neumann, and P. S. Oliveto. Fixed parameter evolutionary algorithms and maximum leaf spanning trees: A matter of mutation. In *Parallel Problem Solving from Nature*, PPSN. Springer, 2010. doi:10.1007/978-3-642-15844-5\_21.

476

477

478

13 S. Kratsch and F. Neumann. Fixed-parameter evolutionary algorithms and the vertex cover problem. *Algorithmica*, 65(4):754–771, 2013. URL: https://doi.org/10.1007/s00453-012-9660-4, doi:10.1007/S00453-012-9660-4.

479

480

14 E. Lawler, J. Lenstra, A. Kan, and D. Shmoys. *The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization*. Wiley, New York, 1985.

481

482

483

15 A. Liefooghe, J. Humeau, S. Mesmoudi, L. Jourdan, and E. Talbi. On dominance-based multiobjective local search: design, implementation and experimental analysis on scheduling and traveling salesman problems. In *Journal of Heuristics*, 2012. doi:10.1007/s10732-011-9181-3.

484

485

16 F. Neumann and A. M. Sutton. *Parameterized Complexity Analysis of Randomized Search Heuristics*. Springer International Publishing, 2020. doi:10.1007/978-3-030-29414-4\_4.

486

487

17 L. Paquete, M. Chiarandini, and T. Stützle. On local optima in multiobjective combinatorial optimization problems. *Annals of Operations Research*, 156:83–97, 2007.

488

489

490

18 L. Paquete and T. Stützle. A study of stochastic local search algorithms for the multiobjective traveling salesman problem. *Metaheuristics for Multiobjective Optimisation*, 535:177–199, 2004.

491

492

493

19 A. Sutton, F., and S. Nallaperuma. Parameterized runtime analyses of evolutionary algorithms for the planar euclidean traveling salesperson problem. *Evol Comput*, 2014. doi:10.1162/EVCO_a_00119.

494

495

496

20 A. M. Sutton and F. Neumann. A parameterized runtime analysis of simple evolutionary algorithms for makespan scheduling. Springer, 2012. URL: https://api.semanticscholar.org/CorpusID:263364089.