  The learning complexity of special sets of vertices in graphs is studied in
the model(s) of exact learning by (extended) equivalence and membership
queries. Polynomial-time learning algorithms are described for vertex covers,
independent sets, and dominating sets. The complexity of learning vertex sets
of fixed size is also investigated, and it is shown that the k-element vertex
covers in a graph can be learned in a number of rounds of interaction that is
independent of the size of the graph. Apart from the elegance of these
algorithmic problems, the chief motivation is the surprising recently
established connection between the important unsolved problem of the learning
complexity of CNF (or DNF) formulas and the learning complexity of dominating
sets. The complexity of teaching sets of vertices in graphs is also considered.
