# $k$-Opt TSP Local Search is NOT exact when $k = \lceil |V|/2 \rceil$

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$$.

The exercise I'm interested in claims that

$$k$$-Opt with $$k = \lceil n/2 \rceil$$ is not exact.

I've tried my hand and searched around but couldn't make it.

I found the paper "Some Examples of Difficult Traveling Salesman Problems", available here (and Papadimitriou is one of the authors by the way). It contains a family of examples for which $$k$$-Opt with $$k < (3n/8)$$ is not exact, and uses a particular kind of subgraph (which it calls the diamond) to impose a structure on feasible tours.

I've tried to replicate and extend something like this with little success.

• @InuyashaYagami I guess in theory any one counter example suffices (so you can pick $n$). A family would be nice, though, specifically in the sense that it holds for arbitrarily large $n$ (rather than it being true as a quirk of some specific value of $n$). Feb 16, 2022 at 14:26

Please see the following figure for $$n = 8$$. All the red and black edges have weight $$1$$. The green edge $$(C,H)$$ has weight $$2$$. And, the blue edges have weight $$0$$. The edges that are not there have weight $$\infty$$; I have not drawn these edges for simplicity.

Now, note that the cycle $$(A,B,C,D,E,F,G,H)$$ is the optimal tour with weight $$5$$. Also, the tour formed by the colored edges (red, green, and blue) has weight $$6$$. Note that the tour formed by these colored edges is locally optimal to $$\lceil n/2 \rceil$$ change but it is not globally optimal.

Why colored tour is locally optimal?

Proof: For the sake of contradiction assume that it is not locally optimal. It means that there exist at most four edges in the tour that can be replaced to obtain a smaller weight tour. Observe that to obtain a smaller weight tour, the edge $$(C,H)$$ must be replaced and the blue edges can not to be replaced. If we replace edge $$(C,H)$$, then we must add the edges $$(C,B)$$ and $$(A,H)$$; otherwise, the weight of the tour will become $$\infty$$.

After adding these edges, we can not keep edges $$(B,D)$$ and $$(A,G)$$ in the tour. Therefore, we must add edges $$(D,E)$$ and $$(G,F)$$; otherwise, the weight of the tour will become $$\infty$$. Now, we must remove edges $$(B,E)$$ and $$(A,F)$$.

To complete the tour, we need to add edge $$(A,B)$$; however, we can not add any more edges since we have already added $$4 = n/2$$ new edges. Therefore, a tour can only be formed by adding edges $$(B,F)$$ and $$(E,A)$$. It makes the weight of the tour $$\infty$$.

This proves that the tour formed by colored edges is locally optimal.

The technique can be easily generalized to the general value of $$n$$. For example, see the following figure for $$n = 14$$. Here, again, the tour formed by the colored edges is locally optimal to $$\lceil n/2 \rceil$$ change but it is not globally optimal.

• I like this a lot! Ingenious. Feb 16, 2022 at 23:32
• @Fimpellizzeri Thanks! Hope I have not made any mistake. Also, I would recommend you to create a separate question post for the second question if possible. The community generally does not advice to ask more than two questions in the same post 😅. Feb 16, 2022 at 23:39
• You've made a typo in saying we couldn't keep $(A, H)$, you most definitely meant $(A, G)$, but I could follow along the parts that felt less clear. After removing $(C, H)$, $(A, H)$ must be added because blue edges must be kept and it's the only cost-feasible way to keep the tour going from $H$ (each vertex in the tour must have degree $2$). Something similar holds for $(C, B)$ with vertex $C$. Now, since we've established that $(A, H)$ and $(H, G)$ must be on the tour, $(G, A)$ can't be on the tour, for it would form a too-short cycle. (Continued...) Feb 16, 2022 at 23:50
• (... continued) Then, $(G, F)$ must be added because it's the only cost-feasible way to keep the tour going from $G$. Something similar holds for the upper part of the graph. But we've already spent all our budget on edge additions, and can only remove one additional edge: either $(A, F)$ or $(B, E)$. Regardless of our choice, this does not lead to a valid tour. Feb 16, 2022 at 23:52
• Do you feel like it would be better to edit this question to be only about $(1)$, and open a second question solely about $(2)$? I could certainly do that, I just worry about hogging the front page. Feb 16, 2022 at 23:53