CSE 521 Assignment #3
Winter 2010

Due: Thursday, February 18, 2010 in class.

Reading Assignment: Kleinberg and Tardos Chapter 7 and Chapter 8.

Instructions: You are allowed to collaborate with fellow students taking the class in solving problem sets. However, you must write up your problem sets individually. If you do collaborate in any way, you must acknowledge for each problem the people you worked with on that problem.

The problems have been chosen for their pedagogical value and hence might be similar or identical to those given out in past offerings of this course at UW, or similar courses at other schools. Using any pre-existing solutions from these sources, from the Web or other algorithms textbooks constitues a violation of the academic integrity expected of you and is strictly prohibited.

Most of the problems require only one or two key ideas for their solution. In writing up your solutions make sure that you clearly write out the main ideas of your solution first so that if you make a mistake in the details you can still get good partial credit for the problem. After you sketch out your solution try to clean up your presentation to make sure that you are only making necessary correct claims since additional incorrect claims will hurt your score.

Please typeset solutions for legibility and hand in hard copies. (The goal for this is not to be time-consuming so don't waste time using drawing programs; hand-drawn diagrams are OK.)

Whether or not the problem asks for it explicitly, you are required to prove that your algorithms do what you claim and give a runtime analysis.

A final piece of advice: Begin work on the problem set early and don't wait till the deadline is only a few days away.

Problems:

  1. Kleinberg and Tardos, Chapter 6, Problem 13, page 324.

  2. Kleinberg and Tardos, Chapter 7, Problem 17, pages 423-424.

  3. Kleinberg and Tardos, Chapter 7, Problem 19, pages 425-426.

  4. We saw how repeatedly augmenting along shortest paths produced a better runtime analysis for general network flow. In this problem you will do something similar in the special case of finding a maximum matching in a bipartite graph G=(V,E) with bipartition V=X+Y, n=|V|, m=|E|.

    At each round the new algorithm will simultaneously augment along all paths in some maximal set Pshort of vertex-disjoint shortest augmenting paths in the flow graph associated with the bipartite matching problem. (In other words, if df(s,t) is the length of the shortest augmenting path in the residual graph Gf then every path in Pshort has length df(s,t) and any other st-path of length df(s,t) shares at least one vertex other than s and t with a path in Pshort.)

    1. Show how to find a set Pshort and do all the augmentations on its paths to get a flow f' in time O(m+n).
    2. Prove that df'(s,t) ≥ df(s,t)+2.
    3. Given two matchings M and M' on graph G we can define the symmetric difference, M Δ M', of M and M' to be the graph consisting of edges that occur in exactly one of the two matchings. M Δ M' consists of a collection of vertex-disjoint paths and cycles (why?). Show that if M' is a maximum matching and flow f corresponds to a matching M of G then
      1. M Δ M' contains exactly |M'|-|M| vertex-disjoint odd-length paths.
      2. Any path of odd length k in M Δ M' corresponds to an augmenting path of length k+2 in Gf.
      3. Use these two properties to prove that once all augmenting paths in Gf. are of length at least k+2 then at most n/k additional augmentations will produce a maximum flow (and hence maximum matching).
    4. Use the above analysis with a suitable value of k to show that this algorithm computes a maximum matching in O(n1/2m) time.

  5. Kleinberg and Tardos, Chapter 8, Problem 3, pages 505-506.