$k$-Opt TSP Local Search is exact when $k = |V| - 1$
I've been self-studying the book Algorithms by <PERSON>, <PERSON> and <PERSON>. 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$. 180
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$. 433