<p>The 2-OPT heuristic for finding TSP tours is fairly close to what you're asking about. It's a local improvement algorithm which looks for sections of a TSP tour which, when reversed, will yield a shorter tour. The 3-OPT and the Lin-Kernighan heuristics work along the same lines, but use more complicated moves. </p>

<p>Looking for the optimal rearrangement of some subpath of a TSP tour is going to be inefficient unless it only involves a short section of this tour, and then I imagine it will be inferior to more global rearrangement algorithms such as 2-OPT (which can reverse a large subpath of a tour).</p>

<p>As far as I know, the concept that you're asking about has no name.</p>

CC BY-SA 2.5
2011-01-24T18:16:16.380Z
2011-01-24T18:16:16.380Z
Peter Shor 
<p>This one has been bugging me for a while. A long time ago in undergrad, I noticed this while learning about TSP. Nobody recognized it and I basically gave up. </p>

<p>Given a hamiltonian path, any subpath will consist of a start, end, and set of interior vertices. Any ordering of the interior vertices will possibly yield a path existing within the graph, that when substituted for the original will yield another valid hamiltonian path. These subpaths would therefore form an equivalence class.</p>

<p>Under this relation, two paths would be equivalent if they have the same start vertex, the same end vertex, and the same set of interior vertices.</p>

<p>Does this equivalence class have a name? If so, are there any TSP optimization algorithms that make use of this?</p>

CC BY-SA 2.5
2011-01-16T02:52:05.377Z
@user3266: Sorry if this is obvious, but how do one permute the order of the interior vertices and construct another valid Hamiltonian path? Or, only if such property exists then you put it into the equivalence class?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-16T03:03:49.443Z
I believe OP means to permute the end nodes?
Ritwik Bose
CC BY-SA 2.5
2011-01-16T03:06:54.240Z
There's a well-known randomized algorithm that uses pivoting, which is similar to this observation. The observation in general, though, is false (if I understand it correctly!): consider a circle.
alpoge
CC BY-SA 2.5
2011-01-16T04:58:51.303Z
I am not sure if you are really referring to an [equivalence class](http://en.wikipedia.org/wiki/Equivalence_class) at all.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-16T06:08:49.597Z
The set of all pairs of vertices that admit a Hamiltonian path?
Jeffε
<graph-theory><co.combinatorics><graph-algorithms><hamiltonian-paths><terminology>
Searching for name of equivalence property in hamiltonian paths
user3266
# Searching for name of equivalence property in hamiltonian paths

(Asked by: username_0 on 2011-01-16)

This one has been bugging me for a while. A long time ago in undergrad, I noticed this while learning about TSP. Nobody recognized it and I basically gave up.

Given a hamiltonian path, any subpath will consist of a start, end, and set of interior vertices. Any ordering of the interior vertices will possibly yield a path existing within the graph, that when substituted for the original will yield another valid hamiltonian path. These subpaths would therefore form an equivalence class.

Under this relation, two paths would be equivalent if they have the same start vertex, the same end vertex, and the same set of interior vertices.

Does this equivalence class have a name? If so, are there any TSP optimization algorithms that make use of this?

**Tags:** graph-theory, co.combinatorics, graph-algorithms, hamiltonian-paths, terminology

> **Comments:**
> **username_1**: @username_0: Sorry if this is obvious, but how do one permute the order of the interior vertices and construct another valid Hamiltonian path? Or, only if such property exists then you put it into the equivalence class?  
> **username_2**: I believe OP means to permute the end nodes?  
> **username_3**: There's a well-known randomized algorithm that uses pivoting, which is similar to this observation. The observation in general, though, is false (if I understand it correctly!): consider a circle.  
> **username_4**: I am not sure if you are really referring to an [equivalence class](http://en.wikipedia.org/wiki/Equivalence_class) at all.  
> **username_5**: The set of all pairs of vertices that admit a Hamiltonian path?  

---

## 1 answers

### Answer by username_6 on 2011-01-24. Score: 3

The 2-OPT heuristic for finding TSP tours is fairly close to what you're asking about. It's a local improvement algorithm which looks for sections of a TSP tour which, when reversed, will yield a shorter tour. The 3-OPT and the Lin-Kernighan heuristics work along the same lines, but use more complicated moves.

Looking for the optimal rearrangement of some subpath of a TSP tour is going to be inefficient unless it only involves a short section of this tour, and then I imagine it will be inferior to more global rearrangement algorithms such as 2-OPT (which can reverse a large subpath of a tour).

As far as I know, the concept that you're asking about has no name.


---

