An independent set of a graph G is a subset of vertices S such that
there is no edge with both endpoints in S.
The maximum independent set of a graph is the largest such empty induced
subgraph.
The need to find large independent sets arises in dispersion problems
associated with facility location and coding theory, as discussed in
catalog Section 
.
The natural state space for a simulated annealing solution would be
all 
subsets of the vertices, represented as a bit vector.
As with maximum cut above, a simple transition mechanism would be
to add or delete one vertex from S.
One natural cost function for subset S might be 0 if S contains an edge,
and |S| if it is indeed an independent set.
This function ensures that we work towards an independent set at all times.
However, this condition is strict enough that we are liable to move only
in a narrow portion of the possible search space.
More flexibility in the search space and quicker cost function
computations can result from allowing non-empty graphs at the early
stages of cooling.
Better in practice would be a cost function like
, where 
is a constant,
T is the temperature,
and 
is the number of edges in the subgraph induced by S.
The dependence of C(S) on T ensures that the search will drive
the edges out faster as the system cools.