This paper reports work investigating various evolutionary approaches to vertex cover (VC), a well-known NP-Hard optimization problem. Central to each of the algorithms is a novel encoding scheme for VC and related problems that treats each chromosome as a binary decision diagram. As a result, the encoding allows only a (guaranteed optimal) subset of feasible solutions. The encoding also incorporates features of a powerful traditional heuristic for VC that allow initial evolutionary algorithm (EA) populations to be seeded in known promising regions of the search space. The resulting EAs have displayed exceptionally strong empirical performance on various vertex cover, independent set, and maximum clique problem classes.