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

(a)

The algorithm of Figure 17.7 keeps selecting vertices from A until we either have a cover or all vertices of A have been included in the cover A' that is being constructed. Therefore, when the algorithm terminates without a cover, A' = A and A does not cover all vertices of B. So the given bipartite graph has no cover.

(b)

Consider the 9 vertex bipartite graph with A = {1, 2, 3}; B = {4, 5, 6, 7, 8, 9}; and edges {(1,4), (1,5), (1,6), (1,7), (2,6), (2,7), (2,8), (3,4), (3,5), (3,9)}. The cover constructed by the greedy algorithm of Figure 13.7 is {1, 2, 3}. The minimum cover is {2, 3}.