Data Structures, Algorithms, & Applications in C++
Chapter 17, Exercise 25

(a)

Start by selecting the vertex with minimum degree. Select additional vertices for inclusion in the independent set in stages, one vertex is selected in each stage. In each stage, determine those vertices that are not adjacent to any currently selected vertex. These are the candidates from which the next vertex must be selected. For each candidate determine how many other candidates it is adjacent to. Select the vertex for which this number is minimum.

(b)

The heuristic works, for example, on the four vertex graph with zero edges. All vertices are included in the independent set. The heuristic fails, for example, on the six vertex graph with edges {(1,2), (1,3), (2,4), (2,5), (3,4), (3,5), (4,5), (4,6), (5,6)}. If the heuristic starts by selecting vertex 1, then only a two vertex independent set is found. The max independent set is {2,3,6}.

(c)

To implement the algorithm of (a), we use an array c to keep track of the candidate and selected vertices. c[i] = 1 if vertex i has been selected for the independent set; c[i] = 0 if vertex i cannot be selected for the independent set (this happens when vertex i is adjacent to at least one of the selected vertices); and c[i] = 2 if vertex i is still a candidate for selection (this requires that vertex i not be adjacent to any vertex that is already selected). Another array count such that count[i] is the number of candidate vertices that candidate vertex i is adjacent to is also used.

At each stage, we select, for inclusion in the independent set, from vertices with c[i] = 2 a vertex minV with minimum count value. c[minV] becomes 1 and we must update the c and count values for the remaining candidates. Former candidates that are adjacent to the newly added vertex minV are no longer candidates. Former candidates that are not adjacent to the newly added vertex minV remain candidates but their count count value may decrease because some of the eliminated vertices may be adjacent to them. To update the count values, we examine the vertices adjacent to all eliminated candidates and reduce the count of their adjacent vertices.