2
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ @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? $\endgroup$
    – Hsien-Chih Chang 張顯之
    Jan 16, 2011 at 2:52
  • $\begingroup$ I believe OP means to permute the end nodes? $\endgroup$
    – Ritwik Bose
    Jan 16, 2011 at 3:03
  • $\begingroup$ 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. $\endgroup$
    – alpoge
    Jan 16, 2011 at 3:06
  • $\begingroup$ I am not sure if you are really referring to an equivalence class at all. $\endgroup$
    – Tsuyoshi Ito
    Jan 16, 2011 at 4:58
  • 3
    $\begingroup$ The set of all pairs of vertices that admit a Hamiltonian path? $\endgroup$
    – Jeffε
    Jan 16, 2011 at 6:08

1 Answer 1

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.