1
$\begingroup$

Wolfram Tech Support has confirmed a bug in FindHamiltonianPath that affects Mathematica 11.3.0 under Windows 10. I reported it when the function would sometimes cause the kernel to quit. The function usually works fine.

When weighted graph G causes the function to fail on my Windows machine, I simply run FindHamiltonianPath@G in MathematicaOnline to get an answer (or a friend runs it on his Mac). The offending weighted graphs seem perfectly normal (unfortunately, I cannot post the geolocation data used to build the graphs).

Has anyone encountered this problem under Windows and if so, did you find a workaround? Thanks.

$\endgroup$
2
$\begingroup$

The context SparseArray contains a routine SparseArray`FindHamiltonianCycle that you might use as a workaround. I am not sure, maybe it is also used as backend for FindHamiltonianCycle and FindHamiltonianPath. (I belief that it's not.) Just give it a try.

SparseArray`FindHamiltonianCycle works on sparse matrices, so the AdjacencyMatrix of your graph has to be supplied. Since it only searches for cycles, we just add an artificial vertex that is connected to all other vertices and remove it later. This can be done by appending a row and a column of ones.

G = RandomGraph[{10, 20}, VertexLabels -> "Name"];

a = SparseArray[ConstantArray[1, {1, VertexCount[G]}]];
A = ArrayFlatten[{
    {AdjacencyMatrix[G], Transpose[a]},
    {a, 0}
    }];
path = SparseArray`FindHamiltonianCycle[A];
i = FirstPosition[path, VertexCount[G] + 1][[1]];
hpath = Join[path[[i + 1 ;;]], path[[1 ;; i - 1]]]

HighlightGraph[G, UndirectedEdge @@@ Partition[hpath, 2, 1]]

enter image description here

The drawback of this method is that it is randomized, so you will usually get a different path when calling SparseArray`FindHamiltonianCycle again.

$\endgroup$
  • $\begingroup$ Thanks for the reply, Henrik. Your idea gave me hope but alas, the problem persists when using FindHamiltonianPath@G (this finds a shortest Hamiltonian path -- SHP -- and not simply a path on the edge-weighted complete graph G). I took your idea and created a SHP from the TSP tour returned by FindShortestTour@G. Now FindShortestTour is causing the kernel to quit in some instances. I'll bring this to Tech Support's attention. $\endgroup$ – bcolletti May 20 '18 at 4:46
  • $\begingroup$ Yes, you should report to support in any case. This is the only way we can hope for better implementations in the future! $\endgroup$ – Henrik Schumacher May 20 '18 at 8:42

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.