The Gn,m Phase Transition is Not Hard for the Hamiltonian Cycle Problem
  Using an improved backtrack algorithm with sophisticated pruning techniques,
we revise previous observations correlating a high frequency of hard to solve
Hamiltonian Cycle instances with the Gn,m phase transition between
Hamiltonicity and non-Hamiltonicity. Instead all tested graphs of 100 to 1500
vertices are easily solved. When we artificially restrict the degree sequence
with a bounded maximum degree, although there is some increase in difficulty,
the frequency of hard graphs is still low. When we consider more regular graphs
based on a generalization of knight's tours, we observe frequent instances of
really hard graphs, but on these the average degree is bounded by a constant.
We design a set of graphs with a feature our algorithm is unable to detect and
so are very hard for our algorithm, but in these we can vary the average degree
from O(1) to O(n). We have so far found no class of graphs correlated with the
Gn,m phase transition which asymptotically produces a high frequency of hard
instances.
