Algorithm Design Techniques

 COMP-360              Assignment 3           Due: Beginning of class, Tues Oct 16

Late assignments  -10% per day, including weekends.
Please give late assignments to Perouz (T.A) in McConnell 232
If you work closely with someone else, indicate the person's name(s) on your homework.
The final write-up of each assignment must, however, be your own work.

1.  Let G=(V,E) be a directed graph. A vertex cover is a subset S of vertices such that each edge in E has at least one endpoint in S. Eg. the set V itself is a vertex cover, and remains a vertex cover if one vertex is deleted. The size of the cover is the number of vertices in S.
(a) Show that the size of any matching (eg. number of matching edges) in G is less than or equal to the size of any vertex cover in G. (Note G may be non-bipartite.)
(b) Show how to find the minimum size vertex cover in a bipartite graph by using network flows. (Hint: study the optimum matching and the residual graph at termination). Prove the size of a minimum vertex cover is the same as the size of a maximum matching.
Illustrate by constructing a graph with 6 vertices in each part, and a maximum matching of size 5. Show the vertex cover.

2.  Text p. 415, question 3 (a) (b). In each case show the maximum flow and the minimum cut.

3. Suppose you have a network and find its max flow f and minimum cut (A,B). Now you increase the capacity of every edge by one. Is it still true that (A,B) gives a minimum cut? Give a proof or counterexample.

4. Text p. 423 problem 16.