Some experimental and theoretical results on test case generators for the maximum clique problem

The authors describe and analyze test case generators for the maximum clique problem (or equivalently for the maximum independent set or vertex cover problems). The generators produce graphs with specified number of vertices and edges, and known maximum clique size. The experimental hardness of the test cases is evaluated in relation to several heuristics for the maximum clique problem, based on neural networks, and derived from the work of A. Jagota. The present 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 for random graphs of that density; the size of the range depends on the density of the graph. The authors also show that one of the algorithms, based on reinforcement learning techniques, has more success than the others at solving the test cases produced by the generators. In addition, NP-completeness reductions are presented 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 constant edge denstiy and a constant ratio of the maximum clique size to the number of vertices, for almost all valid combinations of such values. Moreover, the set of all graphs produced by the generators, and having a constant ratio and edge density, is also NP-hard for almost all valid parameter combinations.