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}

enter image description here enter image description here

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}

enter image description here enter image description here

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.

  • $\begingroup$ 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} $\endgroup$ Sep 8 '13 at 18:58
  • $\begingroup$ @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... $\endgroup$ Sep 8 '13 at 20:50
  • $\begingroup$ You should probably report it to support. $\endgroup$
    – Szabolcs
    Sep 12 '13 at 15:24
  • $\begingroup$ @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...? $\endgroup$ Sep 12 '13 at 15:27
  • 1
    $\begingroup$ 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? $\endgroup$
    – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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