# FindHamiltonianCycle is not invariant to edge permutation

Bug introduced in 9.0.1 or earlier and fixed in 10.0

Found this bug-like behaviour today: if the order of edges is changed so that VertexList does not return the vertices in canonical order, FindHamiltonianCycle is not always able to find the Hamiltonian cycle, that is obviously there.

edges = {1 -> 2, 2 -> 3, 3 -> 1, 1 -> 3, 3 -> 4, 4 -> 1};
g1 = Graph[edges, VertexLabels -> "Name", ImagePadding -> 10];
g2 = Graph[RotateLeft@edges, VertexLabels -> "Name", ImagePadding -> 10];

{g1, FindHamiltonianCycle[g1, All], VertexList@g1}
{g2, FindHamiltonianCycle[g2, All], VertexList@g2}


If a vertex list is specified, that might help, but not always:

g3 = Graph[{1, 4, 2, 3}, RotateLeft@edges, VertexLabels -> "Name", ImagePadding -> 10];
g4 = Graph[{4, 1, 3, 2}, RotateLeft@edges, VertexLabels -> "Name", ImagePadding -> 10];

{g3, FindHamiltonianCycle[g3, All], VertexList@g3}
{g4, FindHamiltonianCycle[g4, All], VertexList@g4}


Is this a bug? If so, at least it is consistent with HamiltonianGraphQ:

HamiltonianGraphQ /@ {g1, g2, g3, g4} ==> {True, False, True, False}


Mathematica 9.0.1, Windows 7, x64.

-
It seems to work OK if you also specify the vertex set: g2 = Graph[Range@4, RotateLeft@edges, VertexLabels -> "Name", ImagePadding -> 10];{g2, FindHamiltonianCycle[g2, All], VertexList@g2} – Dr. belisarius Sep 8 '13 at 18:58
@belisarius As you can see in my g3 and g4 examples, that is not always true. Surely, if the vertex list and the edge list comply in some undocumented sense (even if it is simply canonical ordering) it works, I think it is unwanted behaviour. Waiting for TechSupport at the moment... – István Zachar Sep 8 '13 at 20:50
You should probably report it to support. – Szabolcs Sep 12 '13 at 15:24
@Szabolcs I did, with several other issues still in the pipeline, but the TechSupport web interface is broken (throws error when submitted), and they were unable to help me via the chat. No reply to emails yet. Perhaps someone knows what is going on at WRI support...? – István Zachar Sep 12 '13 at 15:27
I tagged this as a bug. According to the docs, FindHamiltonianCycle only returns {} if no such cycle exists. Unfortunately I couldn't get the Combinatorica version to work on directed graphs. Did you receive a reply from support? – Szabolcs Sep 16 '13 at 17:04

This is a bug: Technical Support gave the following answer acknowledging the problem:

"It does appear that the input you mention is not behaving properly, and I have forwarded an incident report to our developers [...]"

No workaround solution was offered, but there are at least two ways to overcome the problem:

1. Supply correctly sorted vertex names with Graph (as in Graph[{1, 2, 3, 4}, ...]). Since we don't know what is the required vertex order (might not be standard sorting), this is not sure to succeed.
2. Undirect the graph using UndirectedGraph and check for Hamiltonian cycles in the undirected graph. If it finds any, convert UndirectedEdge-s to DirectedEdges in the found cycles, and check for all found cycle whether the original directed graph contains
1. all the re-directed edges AND/OR
2. all the re-directed edges in reverse order.

The latter should be failsafe.

-