Our results show that the hardness of the graphs produced by this method depends in a crucial way on the construction parameters; for a given edge density, challenging graphs can only be constructed using this method for a certain range of maximum clique values; the location of this range depends on the expected maximum clique size of random graphs of that density; the size of the range depends on the density of the graph. In addition, one of the algorithms, based on reinforcement learning techniques, has more success than the others at solving the test cases produced by the generators.
We also present some NP-completeness results showing that (in spite
of what might be suggested by the results just mentioned) the maximum
clique problem remains NP-hard even if the domain is restricted to
graphs having a given constant edge density and a constant ratio of
the maximum clique size to the number of vertices, for all valid
combinations of such values.
Paper available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-69.ps
DIMACS Home Page