Graph Algorithms the Fun Way

17 CLIQUES, INDEPENDENT SETS, AND VERTEX COVERS

In the previous chapter, we saw how the seemingly simple problem of assigning colors rapidly explodes into costly searches. Here, we consider the similarly challenging problems of assembling sets of nodes that satisfy various criteria: maximum cliques, maximum independent sets, and minimum vertex covers.

For each of these problems, we want to find the largest or smallest set of nodes that fulfills some criteria based on immediate neighbors or adjacent edges. While it is easy to check whether a single proposed solution satisfies various constraints, it can be computationally expensive to find ...