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.