DIMACS TR: 93-69

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

Authors: Laura A. Sanchis and Arun Jagota


We 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. We also compare the performance of the different algorithms on the generated graphs.

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