Generating hard and diverse test sets for NP-hard graph problems Original Research Article

In evaluating the performance of approximation algorithms for NP-hard problems, it is often necessary to resort to empirical testing. In order to do such testing it is useful to have test instances of the problem for which the correct answer is known. We present algorithms for efficiently generating test instances for some NP-hard graph problems in such a way that the sets of instances generated can be shown to be both diverse and computationally hard. The techniques used involve combining extremal graph theory results with NP-hardness reductions.