This module discusses two problems from graph
theory that have important applications - the Vertex Cover problem and
the Dominating Set problem.  While the problems appear to be similar,
they differ in the amount of time needed to find a solution.  Although
both problems seem to require exponential time relative to the size of
the graph, the Vertex Cover problem has special properties that allow
it to be solved faster than the Dominating Set problem.  We introduce
an integer programming representation for each problem and discuss
some methods to solve integer programs.  To illustrate the difference
between the Vertex Cover and Dominating Set problems, we present rules
for preprocessing the Vertex Cover problem that effectively reduce its
complexity.
