Question:
can the shortest Hamilton cycle in a complete symmetric graph with weighted edges be constructed from the shortest Hamilton path in the same graph by connecting its ends and then exchanging pairs of non-optimal edges in the order they are encountered when traversing the Hamilton path?
$\begingroup$
$\endgroup$
3
asked Sep 17, 2023 at 11:30
-
$\begingroup$ What kind of edge exchanges are allowed? $\endgroup$– Jukka KohonenCommented Oct 7, 2023 at 7:51
-
$\begingroup$ @JukkaKohonen any kind of exchanges are allowed; I wonder however whether chained 2-opt moves suffice for finding the optimal tour... $\endgroup$– Manfred WeisCommented Oct 7, 2023 at 14:08
-
$\begingroup$ Any kind of exchanges of two edges $ab$ and $cd$ into $ad$ and $bc$? (If you allow "any" exchange of any number of edges to any other edges, surely you find the optimum in one such exchange.) Also, between two vertices, can the edges in opposite directions have different weights? $\endgroup$– Jukka KohonenCommented Oct 7, 2023 at 15:41
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Consider the nine-vertex weighted graph in the figure (left). All edges have the same weight in either direction. Edges not shown are given a high weight, say, $10^6$.
The minimum-weight Hamiltonian path has weight zero (shown in the middle). Connecting its ends, you obtain a Hamiltonian circuit of weight $99$. Any swap of two edges $(a,b),(c,d)$ into $(a,d),(c,b)$ would only increase the weight.
However, the minimum-weight Hamiltonian circuit has weight $3$ (on the right).
Note that here an exhaustive search over triples of edges would find the optimum in one move. However, a similar construction with four chords would require finding an exchange of four edges (and the same idea can be extended arbitrarily).
answered Oct 7, 2023 at 17:59
-
$\begingroup$ nice counter example for the general case. It would be interesting to learn about the situation for metric graphs or for embeddings in the euclidean plane. $\endgroup$ Commented Oct 8, 2023 at 6:49
-
$\begingroup$ You can make the graph metric by adding $M$ to each edge weight, where $M$ is the maximum weight in the original graph. The situation with the Hamiltonian paths and circuits does not change. And of course any metric on $n$ points could be embedded as a Euclidean metric in $n-1$ dimensions. $\endgroup$ Commented Oct 8, 2023 at 7:14
-
$\begingroup$ What happens in low-dimensional Euclidean spaces, I have no idea. I hear they are cool places to live in. $\endgroup$ Commented Oct 8, 2023 at 7:14