  Predicting and comparing algorithm performance on graph instances is
challenging for multiple reasons. First, there is usually no standard set of
instances to benchmark performance. Second, using existing graph generators
results in a restricted spectrum of difficulty and the resulting graphs are
usually not diverse enough to draw sound conclusions. That is why recent work
proposes a new methodology to generate a diverse set of instances by using an
evolutionary algorithm. We can then analyze the resulting graphs and get key
insights into which attributes are most related to algorithm performance. We
can also fill observed gaps in the instance space in order to generate graphs
with previously unseen combinations of features. This methodology is applied to
the instance space of the Hamiltonian completion problem using two different
solvers, namely the Concorde TSP Solver and a multi-start local search
algorithm.
