## 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

**
ABSTRACT
**

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