$k$-Opt TSP Local Search is exact when $k = |V| - 1$

Question

I've been self-studying the book Algorithms by Papadimitriou, Dasgupta and Vazirani. I am having a hard time with a question about local search involving the traveling salesman problem (TSP).

We'll say a local search algorithm is exact if it always returns a globally optimal solution.

Consider a local search algorithm for TSP that uses neighborhoods defined by $k$-change: two tours $T_0$ and $T_1$ are neighbors if one can delete $j \leqslant k$ edges from $T_0$ and add back another $j$ edges to obtain $T_1$. This is known as the $k$-Opt algorithm.

It's easy to see and the book itself discusses how for low values of $k$ (relative to the number $n$ of vertices), $k$-Opt may get stuck on locally optimal solutions that are not globally optimal. In other words, $k$-Opt is not exact for these values of $k$.

In fact, in a previous question, it was shown $k$-Opt is not exact for $k = \lceil n/2 \rceil$. Now, I'd like to show that

$k$-Opt is exact for $k = n-1$.

I have a near solution which I describe below.

---

Given an optimal tour $T^*$ , if some tour $T$ shares at least one edge with $T^*$, then $(n-1)$-change can take $T$ directly to $T^*$.

For $n\geqslant 5$, we can have a tour $T_0$ which shares no edge with a given optimal tour $T^*$.
Suppose there were intermediate tour $T_1$ that uses only edges from $T_0$ and $T^*$, and at least one edge from each.

It's not too hard to see that in this situation, $T_1$ will have at least two edges from each of $T_0$ and $T^*$, though I couldn't make much use of this.

Now, for such a tour $T_1$, there are three cases:

• $\text{cost}(T_1) < \text{cost}(T_0)$.

This is the easiest. Either $\text{cost}(T_1) = \text{cost}(T^*)$ and we're done, or else in another move we can take $T_1$ to $T^*$ (since they now share at least one edge).

• $\text{cost}(T_1) = \text{cost}(T_0)$

In this case, $\text{cost}(T_1\setminus T_0) = \text{cost}(T_0\setminus T_1)$.
By construction $T_1\setminus T_0$ is a subset of the edges in $T^*$, so we can remove those edges in $T^*$ and replace them with $T_0\setminus T_1$. This replacement has no cost change, and hence leads to another globally optimal solution $T'$.
$T'$ is then a globally optimal solution that shares at least one edge with $T_0$, and is hence reachable from $T_0$ in a single move.

• $\text{cost}(T_1) > \text{cost}(T_0)$

We show this case is not possible. If it were, then $\text{cost}(T_1\setminus T_0) > \text{cost}(T_0\setminus T_1)$.
Like above, we could then remove the edges $T_1\setminus T_0$ from $T^*$ and replace them with $T_0\setminus T_1$. This time however, $\text{cost}(T^*)$ would decrease, contradicting the global optimality of $T^*$.

---

The only missing piece would be to show the existence of $T_1$. I could solve examples drawn by hand but have had trouble showing this formally.

I would also like to add that the the existence of $T_1$ must be guaranteed (under the assumption that $(n-1)$-Opt is exact). Indeed, we can handcraft this scenario as follows.

Consider a complete graph $G = (V, E)$ with $n = |V| ⩾ 5$. Let $T^*$ and $T_0$ be edge-disjoint tours in $G$.
Let edges in $T^*$ cost $0$, edges in $T_0$ cost $1$ and all other edges in $E$ have infinite cost (or anything $> n$).

Then any tour that improves on $T_0$ must do so by using some edge with cost $0$ (that is, some edge in $T^*$) and no edge with infinite cost.
Hence, if $(n-1)$-Opt is exact, it must be able to improve on $T_0$, and must do so by taking $T_0$ to a tour that uses only edges from $T_0$ and $T^*$, and at least one edge from each, as desired.

---

Of course, feel free to provide an answer that goes in an entirely different direction; it need not build on my unfinished work.

Answer 1

Searching more on the topic, I've found this post on Math SE with a much stronger result that in particular implies the existence of $T_1$ as defined above. I will reproduce it here to keep things self-contained and prevent question deletions from rendering this answer meaningless.

---

It is true that

Given two edge-disjoint Hamiltonian cycles, there is a different pair of edge-disjoint Hamiltonian cycles with the same union.

This follows from a result of Thomason, published in Section 2 of

Thomason, A.G., Hamiltonian Cycles and Uniquely Edge Colourable Graphs, Ann. Discrete Math. 3, 259-268 (1978).

The rest of this answer describes how that result applies.

Given a multigraph $G = (V,E)$, possibly having loops, define a Hamiltonian pair to be a pair $\{h,\bar{h}\}$ of edge-disjoint Hamiltonian cycles in $G$. Note that there are different conventions for counting Hamiltonian cycles of multigraphs. For our purposes, the "fat triangle" consisting of three vertices, each pair of which is joined by two edges, has four distinct Hamiltonian pairs.

A Hamiltonian cycle can be picked in $2^3$ ways (for each pair of vertices, choose one of two edges connecting them), and uniquely defines the other possible cycle in the pair (for each pair of vertices, use the edge that was not chosen).
Since which cycle was picked first doesn't matter, the result is $2^3/2 = 4$.

Let $P_G$ denote the set of Hamiltonian pairs of $G$.
For $e, e'\in E$, let $P_G(e, e')$ be the set of Hamiltonian pairs of $G$ for which $e$ and $e'$ lie in the same cycle.

Note that if $x$ is a vertex of $G$ and $G$ is $4$-regular, then $x$ is the endpoint of exactly four edges, say $e_1$, $e_2$, $e_3$, $e_4$, and $P_G = \bigsqcup_{i=2}^4 P_G(e_1,e_i)$, where the union is disjoint. It follows that $|P_G| = \sum_{i=2}^4 |P_G(e_1,e_i)|$.

THEOREM (Thomason): If $G$ is a $4$-regular multigraph with at least three vertices and $e$ and $e'$ are two edges of $G$, then $|P_G(e, e')|$ is even.

By our earlier observation, which is made in Thomason's paper, if one can prove that $|P_G(e_1, e_i)|$ is even for all $i = 2, \dots, 4$, it will follow that $|P_G|$, the number of Hamiltonian pairs, is even.

Now, let $G$ be the union of two edge-disjoint Hamiltonian cycles on $n$ vertices, viewed as subgraphs of $K_n$ (the complete graph on $n$ vertices). Then $G$ is a $4$-regular graph.

One Hamiltonian pair is given by taking the two Hamiltonian cycles defining $G$. Since one can assume $G$ has at least three vertices, using Thomason's result, one can produce another Hamiltonian pair in $G$, which is necessarily a Hamiltonian decomposition of $G$ because $G$ is $4$-regular.

NOTE: At this point we already have what we need: either cycle in the second Hamiltonian pair is a valid $T_1$.

Thomason goes on to prove the stronger result that if $m \ge 1$ and $G$ is a $2m$-regular multigraph with at least three vertices, then $G$ has at least $(3m-2)(3m-5)...7 \cdot 4$ Hamiltonian decompositions. In particular, $4$-regular graphs have at least $4$ distinct Hamiltonian pairs.

NOTE: In our particular case, $G$ is the union of two edge-disjoint Hamiltonian cycles. This means that for any Hamiltonian cycle $C$ in $G$ there's exactly one Hamiltonian cycle that is edge-disjoint from $C$. In other words, any two distinct Hamiltonian pairs are disjoint.
It follows that for our $G$, there are at least $6$ Hamiltonian cycles which work as choices for $T_1$.

Thomason also proves that for every $n \ge 10$, there is a $4$-regular graph on $n$ vertices having exactly $32$ Hamiltonian pairs.

---

I suspect there should be an easier way to go about this, since what I needed to show was much, much weaker then Thomason's result. Nonetheless, this at least confirms that things were in the right direction.

I might take a look at the publishing; if I find something more basic that works here, I will update the answer with it.

---

EDIT: The paper's proof is combinatorially existential in nature (not constructive).

It did point at an earlier work by Sloane (in Hamiltonian Cycles in a Graph of Degree 4) that proved exactly what we needed. However, that theorem was also proven using combinatorial machinery.

There is a hint of 'constructive' technique in the proof using contraction to obtain a Hamiltonian cycle in a graph with one less vertex. It is used primarily to convert the graph to a form ($3$-regular) in which another result applies, but that result itself was proven combinatorially, so I don't think there's much deeper to dig.

I'll leave this up for a while longer to see if someone comes up with something more concrete, or simpler even if existential. If nothing shows up, I'll mark my self-answer as accepted.

---

FINAL EDIT: I'll just mention that the reasoning above shows that $k$-Opt is also exact for $k = |V| - 2$.