A Predictive Data Analytic for the Hardness of Hamiltonian Cycle Problem Instances

In their landmark paper ”Where the Really Hard Problems Are”, Cheeseman et al. describe the relative instance hardness, measured in computation time, of three decision prob- lems (Hamiltonian Cycle, Vertex Coloring, K-satisfiability) and one optimization problem (Traveling Salesman). For these four problems, they identify a single property, an ”order parameter” related to specific instance characteristics, for predicting com- putational hardness. One such characteristic is the probability of a random graph being Hamiltonian (having a Hamiltonian Cycle): it depends on its average vertex degree, which is its order parameter. This Hamiltonian probability goes through a sudden phase transition as the order parameter increases and the hardest problem instances, algorithmically speaking, are found close to this phase transition. As such, the order parameter can be seen as an analytic on instance data useful for predicting runtimes on (exponential time) algorithms. In this study, we replicate the original experiment and extend it with two more algorithms. Our countribution is as follows: first, we confirm their original results. Second, we show that an inversion of their heuristic significantly improves algorithmic performance on the same graphs, at zero extra cost. Third, we show that an advanced pruning algorithm by Vandegriend and Culberson further improves runtimes when run on the same graphs. We conclude that the order parameter based on problem instance data analytics is useful across different algorithms. Fourth, we produce high-resolution online interactive diagrams, which we make available for further research along with all the source code and input data.